#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
int A[MAXN],seg[MAXN*4],sp[MAXN][20],vi[MAXN];
bool ck[MAXN];
int getlog(long long n) { return 63-__builtin_clzll(n); }
int rmq(int l,int r)
{
if(l>r) return -2e9;
int lg=getlog(r-l+1);
return max(sp[l][lg],sp[r-(1<<lg)+1][lg]);
}
void build(int l,int r,int pos)
{
if(l==r)
{
seg[pos]=l;
return ;
}
int mid=(l+r)/2;
build(l,mid,pos*2);
build(mid+1,r,pos*2+1);
if(A[seg[pos*2]]<A[seg[pos*2+1]]) seg[pos]=seg[pos*2+1];
else seg[pos]=seg[pos*2];
}
void update(int l,int r,int i,int val,int pos)
{
if(i<l||r<i) return ;
if(l==r)
{
seg[pos]=val;
return ;
}
int mid=(l+r)/2;
update(l,mid,i,val,pos*2);
update(mid+1,r,i,val,pos*2+1);
if(A[seg[pos*2]]<A[seg[pos*2+1]]) seg[pos]=seg[pos*2+1];
else seg[pos]=seg[pos*2];
}
int get(int l,int r,int u,int v,int pos)
{
if(u<=l&&r<=v) return seg[pos];
int mid=(l+r)/2;
if(v<=mid) return get(l,mid,u,v,pos*2);
if(mid+1<=u) return get(mid+1,r,u,v,pos*2+1);
int a=get(l,mid,u,v,pos*2),b=get(mid+1,r,u,v,pos*2+1);
if(A[a]<A[b]) return b;
return a;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,q;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>A[i];
sp[i][0]=A[i];
}
for(int j=1;(1<<j)<=n;j++) for(int i=1;i<=n-(1<<j)+1;i++) sp[i][j]=max(sp[i][j-1],sp[i+(1<<(j-1))][j-1]);
cin>>q;
build(1,n,1);
for(int i=1;i<=q;i++)
{
int l,r;
cin>>l>>r;
int cnt=min(11,r-l+1);
for(int j=1;j<=cnt;j++)
{
update(1,n,vi[j]=get(1,n,l,r,1),0,1);
ck[vi[j]]=true;
}
int ans=0;
for(int j=l;j<=r;j++) for(int k=j+1;k<=r;k++) for(int x=k*2-j;x<=r;x++)
if(ck[j]+ck[k]+ck[x]>=1) ans=max(ans,A[j]+A[k]+A[x]);
cout<<ans<<"\n";
for(int j=1;j<=cnt;j++) update(1,n,vi[j],vi[j],1),ck[vi[j]]=false;
}
}
