#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

// Standard Range Minimum Query (RMQ) Segment Tree
struct SegTree {
    int n;
    vector<long long> tree;

    SegTree(const vector<long long>& arr) {
        n = arr.size();
        tree.assign(4 * n, 1e18);
        build(arr, 1, 0, n - 1);
    }

    void build(const vector<long long>& arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
            return;
        }
        int mid = start + (end - start) / 2;
        build(arr, 2 * node, start, mid);
        build(arr, 2 * node + 1, mid + 1, end);
        tree[node] = min(tree[2 * node], tree[2 * node + 1]);
    }

    long long query(int node, int start, int end, int L, int R) {
        if (R < start || end < L) return 1e18;
        if (L <= start && end <= R) return tree[node];

        int mid = start + (end - start) / 2;
        long long left_min = query(2 * node, start, mid, L, R);
        long long right_min = query(2 * node + 1, mid + 1, end, L, R);
        return min(left_min, right_min);
    }

    long long query(int L, int R) {
        if (L > R) return 1e18;
        return query(1, 0, n - 1, L, R);
    }
};

long long getMaxSubarraySumWithSegTree(const vector<long long>& arr) {
    int n = arr.size();

    // 1-indexed prefix sums
    vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        prefix[i + 1] = prefix[i] + arr[i];
    }

    // Build RMQ Segment tree over the prefix sums
    SegTree st(prefix);

    unordered_map<long long, int> last_seen, prev_seen, prev2_seen;

    // Track highest 2nd-to-last occurrences
    int p1 = -1, p2 = -1;
    long long val1 = 4e18, val2 = 4e18;

    // Track highest 3rd-to-last occurrence
    int p3 = -1;

    long long max_sum = -1e18;
    bool found_valid = false;

    for (int R = 0; R < n; ++R) {
        long long x = arr[R];

        if (!last_seen.count(x)) {
            last_seen[x] = -1;
            prev_seen[x] = -1;
            prev2_seen[x] = -1;
        }

        prev2_seen[x] = prev_seen[x];
        prev_seen[x] = last_seen[x];
        last_seen[x] = R;

        p3 = max(p3, prev2_seen[x]);

        int new_p = prev_seen[x];
        if (new_p > -1) {
            if (x == val1) {
                p1 = new_p;
            } else if (x == val2) {
                p2 = new_p;
                if (p2 > p1) {
                    swap(p1, p2);
                    swap(val1, val2);
                }
            } else {
                if (new_p > p1) {
                    p2 = p1;
                    val2 = val1;
                    p1 = new_p;
                    val1 = x;
                } else if (new_p > p2) {
                    p2 = new_p;
                    val2 = x;
                }
            }
        }

        // The valid window of prefix indices for starting bound L
        int W_left = max(p2, p3) + 1;
        int W_right = p1;

        if (W_left <= W_right && p1 != -1) {
            // O(log N) Range Minimum Query
            long long min_prefix = st.query(W_left, W_right);

            long long current_sum = prefix[R + 1] - min_prefix;
            max_sum = max(max_sum, current_sum);
            found_valid = true;
        }
    }

    if (!found_valid) return -1e18;
    return max_sum;
}