#include<bits/stdc++.h>
#define int long long
#define ls(u) u<<1
#define rs(u) u<<1|1
using namespace std;
const int N=1e5+5;
int n,m,a[N],last[N];
vector<int> vec[N];
struct Tree{
	int l,r;
	int sum,lmx,rmx,mx;
}t[N*4],q[N];
bool cmp(Tree x,Tree y){
	return x.r<y.r;
}
void pushup(Tree &T,Tree L,Tree R){
    T.lmx=max(L.lmx,L.sum+R.lmx); 
    T.rmx=max(R.rmx,R.sum+L.rmx);
    T.mx=max(max(L.mx,R.mx),R.lmx+L.rmx);
    T.sum=L.sum+R.sum; 
}
void build(int u,int l,int r){
	t[u].l=l;
	t[u].r=r;
	if(l==r){
		t[u].sum=t[u].mx=t[u].lmx=t[u].rmx=a[l]; 
		return;
	}
	int mid=(l+r)/2;
	build(ls(u),l,mid);
	build(rs(u),mid+1,r);
	pushup(t[u],t[ls(u)],t[rs(u)]);
}
void update(int u,int x,int v){
    if(t[u].l==t[u].r){
    	t[u].sum=t[u].mx=t[u].lmx=t[u].rmx=v;
        return;
    }
	int mid=(t[u].r+t[u].l)>>1;
    if(x<=mid) update(ls(u),x,v);
    if(x>mid) update(rs(u),x,v);
    pushup(t[u],t[ls(u)],t[rs(u)]);
}
Tree query(int u,int l,int r){
	if(t[u].l>=l&&t[u].r<=r) return t[u];
	int mid=(t[u].l+t[u].r)>>1;
	if(r<=mid) return query(ls(u),l,r);
    if(l>mid) return query(rs(u),l,r);
    Tree T;
    pushup(T,query(ls(u),l,mid),query(rs(u),mid+1,r));
    return T;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
	cin>>m;
	for(int i=1;i<=m;i++){
		q[i].sum=i;
		cin>>q[i].l>>q[i].r;
	}
	sort(q+1,q+1+m,cmp);
	for(int i=1;i<=m;i++) vec[q[i].r].push_back(i);
	for(int i=1;i<=n;i++){
		if(last[a[i]]) update(1,last[a[i]],0);
		last[a[i]]=i;
		for(auto u:vec[i]) q[q[u].sum]=query(1,q[u].l,q[u].r);
	}
	for(int i=1;i<=m;i++) cout<<q[i].mx<<endl;
	return 0;
}