#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mpr make_pair
#define fr first
#define sc second
inline int read(){
	int res=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {res=res*10+(c-'0');c=getchar();}
	return res*f;
}
const int N=1e5+5;
struct tree{
	int tg,mx,ltg,lmx;
};
struct sgm{
	#define lc(x) (x<<1)
	#define rc(x) (x<<1|1)
	tree s[N<<2];
	void push_up(int x){
		s[x].mx=max(s[lc(x)].mx,s[rc(x)].mx);
		s[x].lmx=max(s[lc(x)].lmx,s[rc(x)].lmx);
	}
	void add(int x,int nk,int k,int op){
		if (op==0){
			s[x].tg+=nk;
			s[x].mx+=nk;
		}
		s[x].lmx=max(s[x].lmx,s[x].mx+k);
		s[x].ltg=max(s[x].ltg,s[x].tg+k);
		if (op==1){
			s[x].tg+=nk;
			s[x].mx+=nk;
		}
	}
	void push_down(int x){
		add(lc(x),s[x].tg,s[x].ltg,1);
		add(rc(x),s[x].tg,s[x].ltg,1);
		s[x].tg=s[x].ltg=0;
	}
	void modify(int x,int ql,int qr,int l,int r,int k){
		if (ql<=l&&qr>=r){
			add(x,k,0,0);
			return;
		}
		push_down(x);
		int mid=(l+r)>>1;
		if (ql<=mid) modify(lc(x),ql,qr,l,mid,k);
		if (qr>mid) modify(rc(x),ql,qr,mid+1,r,k);
		push_up(x);
	}
	int query(int x,int ql,int qr,int l,int r){
		if (ql<=l&&qr>=r) return s[x].lmx;
		int res=0,mid=(l+r)>>1;
		push_down(x);
		if (ql<=mid) res=max(query(lc(x),ql,qr,l,mid),res);
		if (qr>mid) res=max(query(rc(x),ql,qr,mid+1,r),res);
		push_up(x); 
		return res;
	}
	#undef lc
	#undef rc
}book;
int n,m,f[N],a[N],mp[N<<1],output[N];
struct query{
	int x,y,i;
	bool operator<(const query &o)const{
		return y<o.y;
	}
}q[N];
signed main(){
	n=read();
	for (int i=1;i<=n;i++){
		a[i]=read();
	    f[i]=mp[a[i]+N]+1;
	    mp[a[i]+N]=i;
	}
	m=read();
    for (int i=1;i<=m;i++){
        int x=read(),y=read();
        q[i]={x,y,i};
	}
	for (int i=0;i<=(N<<2);i++){
		book.s[i].lmx=-1e18;
	}
	sort(q+1,q+m+1);
	int tip=1;
	for (int i=1;i<=m;i++){
	    while (tip<=q[i].y&&tip<=n) book.modify(1,f[tip],tip,1,n,a[tip++]);
		output[q[i].i]=book.query(1,q[i].x,q[i].y,1,n);
	}
	for (int i=1;i<=m;i++) cout<<output[i]<<'\n';
	return 0;
}