RT

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>

#define N 100020
#define K 100001
#define ls (cur<<1)
#define rs (ls+1)
#define mid ((l+r)>>1)
#define inf (int)(1e9+7)

using namespace std;

struct tree {
	int mx,sum,mxtag,sumtag;
}t[N<<2];

struct node {
	int l,r,id;
}q[N];

bool cmp(node x,node y) {
	return x.r<y.r;
}

int a[N],id[N],pre[N],ans[N];
int n,m;

void push_up(int cur) {
	t[cur].sum=max(t[ls].sum,t[rs].sum); //去重！！！ 
	t[cur].mx=max(t[ls].mx,t[rs].mx);
}

void push_down(int cur) {
	t[ls].mx=max(t[ls].mx,t[ls].sum+t[cur].mxtag);
	t[ls].sum+=t[cur].sumtag;
	t[ls].mxtag=max(t[ls].mxtag,t[ls].sumtag+t[cur].mxtag);
	t[ls].sumtag+=t[cur].sumtag;
	
	t[rs].mx=max(t[rs].mx,t[rs].sum+t[cur].mxtag);
	t[rs].sum+=t[cur].sumtag;
	t[rs].mxtag=max(t[rs].mxtag,t[rs].sumtag+t[cur].mxtag);
	t[rs].sumtag+=t[cur].sumtag;
	t[cur].mxtag=t[cur].sumtag=0;
}

void update(int cur,int l,int r,int cl,int cr,int x) {
	if(cl<=l&&r<=cr) {
		t[cur].sum+=x;
		t[cur].mx=max(t[cur].mx,t[cur].sum);
		t[cur].sumtag+=x;
		t[cur].mxtag=max(t[cur].mxtag,t[cur].sumtag);
		return;
	}
	push_down(cur);
	if(cl<=mid) update(ls,l,mid,cl,cr,x);
	if(cr>mid) update(rs,mid+1,r,cl,cr,x);
	push_up(cur);
}

int query(int cur,int l,int r,int cl,int cr) {
	if(cl<=l&&r<=cr) return t[cur].mx;
	push_down(cur);
	int ans=-inf;
	if(cl<=mid) ans=query(ls,l,mid,cl,cr);
	if(cr>mid) ans=max(ans,query(rs,mid+1,r,cl,cr));
	return ans;
}

int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		pre[i]=id[a[i]+K];
		id[a[i]+K]=i;
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++) {
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+1+m,cmp);
	
	int j=1;
	for(int i=1;i<=n;i++) {
		update(1,1,n,pre[i]+1,i,a[i]);
		for(;j<=m&&q[j].r<=i;j++) {
			ans[q[j].id]=query(1,1,n,q[j].l,q[j].r);
		}
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
}