#include<cstdio>

 #include<cstdlib>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 const int nmax=,tmax=<<,shift=nmax;

 int n,m;

 int M=,H=;

 int a[nmax+],last[nmax*+],pre[nmax+];

 ll f[tmax+],g[tmax+],fd[tmax+],gd[tmax+],ans[nmax+];

 int l[nmax+],r[nmax+],p[nmax+];

 bool cmp(int i,int j){

     return r[i]<r[j];

 }

 inline int max(int a,int b) {return a>b?a:b;}

 inline void update(ll &a,ll b){if(a<b) a=b;}

 inline void take(int i){

     f[i]=max(f[i<<],f[i<<|]),g[i]=max(g[i<<],g[i<<|]);

 }

 inline void give(int i,int j){

     //fd[i]和gd[i]在于之前添加时可能没有顾及到下面的节点，于是偷懒加上tag表示这里可以下传的数目；

     //其中gd[i]表示的是历史上给i的子树能添加的最大值，fd[i]表示总计能给它们添加多少

     update(g[i],f[i]+gd[j]),f[i]+=fd[j];

     update(gd[i],fd[i]+gd[j]),fd[i]+=fd[j];

 }

 void pd(int i){

     for(int h=H-,j;h;--h)//枚举i的所有祖先将它们的 tag下传

         if(fd[j=i>>h] || gd[j])

             give(j<<,j),give(j<<|,j),fd[j]=gd[j]=;

 }

 void add(int l,int r,int x){

     //f[i]表示计算从i到当前枚举值的整段之和

     //g[i]表示必须选择i为左端点的情况下，到当前枚举值间的最优值。

     //若g[i]不为叶子节点，则g[i]表示以其代表区间内的任意元素作为左端点的最优值

     //f[i]不为叶节点时等于示以其代表区间内的任意元素作为左端点且当前枚举点为右端点时的最优值

     for(pd(l+=M-),pd(r+=M+)/*传递(L,R)之间的所有标记*/;l^r^;take(l>>=),take(r>>=)/*这里只能传到 L,R会合之下的两端*/){

         //因为不能每次传到底，所以给包含区间加上tag标记

         if(~l&)

             update(g[l^],f[l^]+=x),update(gd[l^],fd[l^]+=x);

         if(r&)

             update(g[r^],f[r^]+=x),update(gd[r^],fd[r^]+=x);

     }

     for(int tmp1,tmp2;l>>=;){//所以这里需要往上带到根节点去

         tmp1=f[l],tmp2=g[l];

         take(l);

         if(f[l]==tmp1 && g[l]==tmp2) break;

     }

 }

 ll getmax(int l,int r){

     //每次从l,r中选任意一个节点作为左端点，右端点不固定时的最优值即为答案。

     ll Ans=;

     for(pd(l+=M-),pd(r+=M+);l^r^;l>>=,r>>=){

         if(~l&) update(Ans,g[l^]);

         if(r&) update(Ans,g[r^]);

     }

     return Ans;

 }

 int main(){

     freopen("hungry.in","r",stdin);

     freopen("hungry.out","w",stdout);

     scanf("%d", &n);

     while(n>=M-) M<<=,++H;

     for(int i=;i<=n;i++)

         scanf("%d",a+i),pre[i]=last[a[i]+shift],last[a[i]+shift]=i;//pre[i]表示上一个和它相同数所在的位置

     scanf("%d",&m);

     for(int i=;i<=m;i++)

         scanf("%d%d",l+i,r+i),p[i]=i;

     sort(p+,p+m+,cmp);//给右区间排序，因为g[x]表示的是从x开始，必须选x到当前枚举值之间的最优值，而当前枚举值相当于区间的右端点 

     for(int i=,j=;i<=n && j<=m;i++)

         for(add(pre[i]+,i,a[i])/*往两个相同的数之间加，这样可以使重复的数只加一次*/;j<=m && r[p[j]]<=i;j++)

                ans[p[j]]=getmax(l[p[j]],r[p[j]]);

     for(int i=;i<=m;i++)

         printf("%I64d\n",ans[i]);

     return ;

 }