#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(19,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]>=2) 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; } }