#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+10;
int n,q;
int a[maxn],pre[maxn],lst[maxn],ans[maxn];
vector<int> b[maxn];
struct type
{
	int l,r,id;
}qu[maxn];
bool cmp(type x,type y)
{
	return x.l<y.l;
}
struct tree
{
	int l,r,sum,lmx,rmx,mx;
}tr[maxn<<2];
tree push_up(tree x,tree y)
{
	tree z;
	z.l=x.l,z.r=y.r;
	z.sum=x.sum+y.sum;
	z.lmx=max(x.lmx,x.sum+y.lmx);
	z.rmx=max(y.rmx,x.rmx+y.sum);
	z.mx=max(max(x.mx,y.mx),x.rmx+y.lmx);
	return z;
}
void build(int id,int l,int r)
{
	tr[id].l=l,tr[id].r=r;
	tr[id].sum=tr[id].lmx=tr[id].rmx=tr[id].mx=0;
	if(l==r) return;
	int mid=(l+r)/2;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	tr[id]=push_up(tr[id*2],tr[id*2+1]);
}
void update(int id,int x,int c)
{
	if(tr[id].l==tr[id].r)
	{
		tr[id].sum=tr[id].lmx=tr[id].rmx=tr[id].mx=c;
		return;
	}
	int mid=(tr[id].l+tr[id].r)/2;
	if(x<=mid) update(id*2,x,c);
	else update(id*2+1,x,c);
	tr[id]=push_up(tr[id*2],tr[id*2+1]);
}
tree query(int id,int l,int r)
{
	if(tr[id].l>=l&&tr[id].r<=r) return tr[id];
	int mid=(tr[id].l+tr[id].r)/2;
	if(l>mid) return query(id*2+1,l,r);
	if(r<=mid) return query(id*2,l,r);
	return push_up(query(id*2,l,r),query(id*2+1,l,r));
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		pre[i]=lst[a[i]+100000];
		lst[a[i]+100000]=i;
		b[pre[i]].push_back(i);
	}
	build(1,1,n);
	cin>>q;
	for(int i=1;i<=q;i++) cin>>qu[i].l>>qu[i].r,qu[i].id=i;
	sort(qu+1,qu+q+1,cmp);
	qu[0].l=0;
	for(int i=1;i<=q;i++)
	{
		for(int j=qu[i-1].l;j<qu[i].l;j++)
			for(auto k:b[j]) update(1,k,a[k]);
		ans[qu[i].id]=query(1,qu[i].l,qu[i].r).mx;
	}
	for(int i=1;i<=q;i++) cout<<max(ans[i],0ll)<<endl;
}