Persistent Tree

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define sz(a) (int)a.size()
#define ms(a, x) memset(a, x, sizeof a)
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef pair<int,int> pt;

const int inf = 1<<30;
const int N = 1<<17;

int a[N], nxt[N];
bool *used = new bool[2000001];
int *last = new int[2000001];

struct node {
    node *l, *r;
    ll mx, pref, suff, sum;
    node() : mx(0), pref(0), suff(0), sum(0), l(NULL), r(NULL) {}
    node(ll val) : mx(val), pref(val), suff(val), sum(val), l(NULL), r(NULL) {}
    node(node *l, node *r) : l(l), r(r) {
        mx = max(l->mx, r->mx);
        mx = max(mx, l->suff + r->pref);
        pref = max(l->pref, l->sum + r->pref);
        suff = max(r->suff, r->sum + l->suff);
        sum = l->sum + r->sum;
    }
} *root[N];

node *build(int l, int r) {
    if (l + 1 == r) {
        if (!used[a[l]]) {
            used[a[l]] = 1;
            return new node(a[l]);
        } else {
            return new node(0);
        }
    } else {
        int mid = (l + r) >> 1;
        return new node(build(l, mid), build(mid, r));
    }
}

node *update(node *v, int l, int r, int pos, int val) {
    if (l + 1 == r) {
        return new node(val);
    } else {
        int mid = (l + r) >> 1;
        if (pos < mid) {
            return new node(update(v->l, l, mid, pos, val), v->r);
        } else {
            return new node(v->l, update(v->r, mid, r, pos, val));
        }
    }
}

node *get(node *v, int l, int r, int L, int R) {
    if (R <= l || r <= L) return new node(-inf);
    if (L <= l && r <= R) {
        return v;
    } else {
        int mid = (l + r) >> 1;
        return new node(get(v->l, l, mid, L, R), get(v->r, mid, r, L, R));
    }
}

void out(node *v, int l, int r) {
    if (l + 1 == r) {
        printf("%lld ", v->sum);
    } else {
        int mid = (l + r) >> 1;
        out(v->l, l, mid);
        out(v->r, mid, r);
    }
}

int main() {
    #ifdef LOCAL
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    #endif

    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
    }

    used += (int)1e6;
    last += (int)1e6;

    for (int i = n-1; i >= 0; i--) {
        nxt[i] = last[a[i]];
        last[a[i]] = i;
    }

    root[0] = build(0, n);

    for (int i = 0; i+1 < n; i++) {
        if (nxt[i] == 0) {
            root[i+1] = update(root[i], 0, n, i, 0);
        } else {
            root[i+1] = update(root[i], 0, n, nxt[i], a[i]);
            root[i+1] = update(root[i+1], 0, n, i, 0);
        }
    }

    for (int i = 0; i < n; i++) {
        out(root[i], 0, n);
        printf("\n");
    }

    int m;
    scanf("%d", &m);
    for (int i = 0, l, r; i < m; i++) {
        scanf("%d %d", &l, &r); l--;
        printf("%lld\n", get(root[l], 0, n, l, r)->mx);
    }

    return 0;
}