题目链接：点击打开链接

每一个点都是最大值，把一整个序列和都压缩在一个点里。

1、普通的区间求和就是维护2个值，区间和Sum和延迟标志Lazy

2、Old 是该区间里出现过最大的Sum, Oldlazy 是对于给下一层的子区间的标志，添加多少是能给子区间添加的值最大的（用来维护Old)

显然对于Old 。要么维持原样，要么更新为稍新的值：即 Sum(id) + Oldlazy

而对于Oldlazy, 要么维持原样，要么变成最新的延迟标记：即 Lazy(id) + Oldlazy

上2行的Oldlazy都是指对这个tree[id]有效的，即他们父节点的Oldlazy - > Oldlazy( id / 2 )

#include <vector>

#include <iostream>

#include <algorithm>

#include <string.h>

#include <stdio.h>

using namespace std;

#define N 100005

#define Lson(x) (x<<1)

#define Rson(x) (x<<1|1)

#define L(x) tree[x].l

#define R(x) tree[x].r

#define Old(x) tree[x].old

#define Sum(x) tree[x].sum

#define Lazy(x) tree[x].lazy

#define Olazy(x) tree[x].oldlazy

inline int Mid(int l, int r){return (l+r)>>1;}

struct Subtree{

	int l, r;

	int old, oldlazy, sum, lazy;

}tree[N<<2];

void push_down(int id){

	if(L(id) == R(id)) return ;

	if(Lazy(id) || Olazy(id)){

		Olazy(Lson(id)) = max(Olazy(Lson(id)), Lazy(Lson(id)) + Olazy(id));

		Old(Lson(id)) = max(Old(Lson(id)), Sum(Lson(id)) + Olazy(id));

		Lazy(Lson(id)) += Lazy(id); Sum(Lson(id)) += Lazy(id);

		Olazy(Rson(id)) = max(Olazy(Rson(id)), Lazy(Rson(id)) + Olazy(id));

		Old(Rson(id)) = max(Old(Rson(id)), Sum(Rson(id)) + Olazy(id));

		Lazy(Rson(id)) += Lazy(id); Sum(Rson(id)) += Lazy(id);

		Lazy(id) = Olazy(id) = 0;

	}

}

void push_up(int id){

	if(L(id) == R(id)) return ;

	Old(id) = max(Old(Lson(id)), Old(Rson(id)));

	Sum(id) = max(Sum(Lson(id)), Sum(Rson(id)));

}

void build(int l, int r, int id){

	L(id) = l; R(id) = r;

	Sum(id) = Old(id) = Lazy(id) = Olazy(id) = 0;

	if(l == r) return ;

	int mid = Mid(l, r);

	build(l, mid, Lson(id)); build(mid+1, r, Rson(id));

}

void updata(int l, int r, int val, int id){

	push_down(id);

	if(l == L(id) && R(id) == r) {

		Sum(id) += val;

		Lazy(id) += val;

		Olazy(id) = max(Olazy(id), Lazy(id));

		Old(id) = max(Old(id), Sum(id));

		return ;

	}

	int mid = Mid(L(id), R(id));

	if(mid < l)

		updata(l, r, val, Rson(id));

	else if(r <= mid)

		updata(l, r, val, Lson(id));

	else {

		updata(l, mid, val, Lson(id));

		updata(mid+1, r, val, Rson(id));

	}

	push_up(id);

}

int Query(int l, int r, int id){

	push_down(id);

	if(l == L(id) && R(id) == r) return Old(id);

	int ans , mid = Mid(L(id), R(id));

	if(mid < l)

		ans = Query(l, r, Rson(id));

	else if(r <= mid)

		ans = Query(l, r, Lson(id));

	else

		ans = max(Query(l, mid, Lson(id)), Query(mid+1, r, Rson(id)));

	push_up(id);

	return ans;

}

int a[N], n, las[N<<1];

struct node{

	int l, r, num, ans;

}query[N];

bool cmp1(node a, node b){return a.r < b.r;}

bool cmp2(node a, node b){return a.num < b.num;}

void solve(){

	int i, q;

	for(i = 1; i <= n; i++)scanf("%d",&a[i]);

	build(1, n, 1);

	scanf("%d",&q);

	for(i = 1; i <= q; i++)scanf("%d %d",&query[i].l, &query[i].r), query[i].num = i;

	sort(query+1, query+q+1, cmp1);

	int top = 1;

	memset(las, 0, sizeof las);

	for(i = 1; i <= n && top <= q; i++){

		updata(las[a[i]+N]+1, i, a[i], 1);

		las[a[i]+N] = i;

		while(query[top].r == i && top <= q){

			query[top].ans = Query(query[top].l, query[top].r, 1);

			top++;

		}

	}

	sort(query+1, query+q+1, cmp2);

	for(i = 1; i <= q; i++)printf("%d\n", query[i].ans);

}

int main(){

	while(~scanf("%d",&n))

		solve();

	return 0;

}