#include<iostream>
#include<cstdio>
#include<bits/stdc++.h>
#define ll long long
#define MAXN 100005
using namespace std;
unsigned ll n,m,a[MAXN],pre[MAXN<<1],cur[MAXN<<1],ans[MAXN];
struct qs{
	ll r=0,l=0,id=0;
	friend bool operator < (qs &a,qs &b){
		return a.r<b.r;
	}
}q[MAXN];

struct ts{
	ll sum=0,sux=0,tag=0,tax=0;
	friend ts operator + (ts &a,ts &b){
		ts c;
		c.sum=max(a.sum,b.sum);
		c.sux=max(a.sux,b.sux);
		return c;
	}
}t[MAXN<<2];
bool cmp(qs a,qs b){
	return a<b;
}
inline ll ls(ll x){
	return x<<1;
}
inline ll rs(ll y){
	return y<<1|1;
}
void in(){
	cin>>n;
	for(ll i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		pre[i]=cur[a[i]+(int)1e5];
		cur[a[i]+(int)1e5]=i;
	}
	cin>>m;
	for(ll i=1;i<=m;i++){
		scanf("%lld%lld",&q[i].l,&q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+m+1);
	return;
}
inline void push_up(ll p){
	t[p]=t[rs(p)]+t[ls(p)];
}
inline void push_down(ll p){
	t[rs(p)].sux=max(t[rs(p)].sux,t[rs(p)].sum+t[p].tag);
	t[ls(p)].sux=max(t[ls(p)].sux,t[ls(p)].sum+t[p].tag);
	t[ls(p)].sum+=t[p].tag;
	t[rs(p)].sum+=t[p].tag;
	t[rs(p)].tax=max(t[rs(p)].tax,t[rs(p)].tag+t[p].tag);
	t[ls(p)].tax=max(t[ls(p)].tax,t[ls(p)].tag+t[p].tag);
	t[rs(p)].tag+=t[p].tag;
	t[ls(p)].tag+=t[p].tag;
	t[p].tag=t[p].tax=0;
	return;
}

/*void build(ll p,ll l,ll r){
	tag[p]=0;
	if(l==r){
		ans[p]=a[l];return;
	}
	ll mid=(l+r)>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	push_up(p);
}*/

inline void update(ll l1,ll r1,ll l,ll r,ll p,ll k){
	if(l1<=l&&r<=r1){
		t[p].sux=max(t[p].sum+k,t[p].sux);
		t[p].sum+=k;
		t[p].tax=max(t[p].tag+k,t[p].tax);
		t[p].tag+=k;
		return;
	}
	push_down(p);
	ll mid=(l+r)>>1;
	if(l1<=mid) update(l1,r1,l,mid,ls(p),k);
	if(r1>mid) update(l1,r1,mid+1,r,rs(p),k);
	push_up(p);
}
ll query(ll x,ll y,ll l,ll r,ll p){
	ll res=0;
	if(x<=l&&y>=r){
		return t[p].sux;
	}
	ll mid=(l+r)>>1;
	push_down(p);
	if(x<=mid) res=max(res,query(x,y,l,mid,ls(p)));
	if(y>mid) res=max(res,query(x,y,mid+1,r,rs(p)));
	return res;
}
int main(){
	ll a1,b,c,d,e,f;ll j=1;
	in();
	for(ll i=1;i<=n;i++){
		b=pre[i]+1,c=i,d=a[i];
		update(b,c,1,n,1,d);
		for(;j<=m&&q[j].r<=i;j++){
			ans[q[j].id]=query(q[j].l,q[j].r,1,n,1);
		}
	}
	for (ll i=1;i<m;i++){
		cout<<ans[i]<<endl;
	}
	cout<<ans[m];
	return 0;
}

一个个往里加叶子数据计算子线段最大值 可是WA了 :( 求调 求调