#include <bits/stdc++.h>
using namespace std;
const int nmax=500005;
vector< pair<int,int> > l[nmax],qr[nmax];
int v[nmax],st[nmax],an[nmax];
int n,i,j,u,q,L,R;
struct node
{
int L,R,LR;
}arb[4*nmax],ans;
void add(int x,int y)
{
if(2*y-x<=n)
l[x].push_back({2*y-x,v[x]+v[y]});
}
void mrg(node &A,node B,node C)
{
A.L=max(B.L,C.L);
A.R=max(B.R,C.R);
A.LR=max(B.LR,C.LR);
A.LR=max(A.LR,B.L+C.R);
}
void update(int nod,int l,int r,int poz,int val,int tip)
{
if(l==r)
{
if(tip) arb[nod].R=max(arb[nod].R,val);
else arb[nod].L=max(arb[nod].L,val);
arb[nod].LR=arb[nod].L+arb[nod].R;
return;
}
int m=(l+r)/2;
if(poz<=m) update(2*nod,l,m,poz,val,tip);
else update(2*nod+1,m+1,r,poz,val,tip);
mrg(arb[nod],arb[2*nod],arb[2*nod+1]);
}
void query(int nod,int l,int r,int st,int dr)
{
if(st<=l&&r<=dr)
{
mrg(ans,ans,arb[nod]);
return;
}
int m=(l+r)/2;
if(st<=m) query(2*nod,l,m,st,dr);
if(m<dr) query(2*nod+1,m+1,r,st,dr);
}
int Q(int S,int D)
{
ans={-(1<<29),-(1<<29),-(1<<29)};
query(1,1,n,S,D);
return ans.LR;
}
int main()
{
//freopen("data.in","r",stdin);
ios_base::sync_with_stdio(false);
cin>>n;
for(i=1;i<=n;i++)
{
cin>>v[i];
while(u>0&&v[i]>v[st[u]])
{
add(st[u],i);
u--;
}
if(u) add(st[u],i);
st[++u]=i;
}
cin>>q;
for(i=1;i<=q;i++)
{
cin>>L>>R;
qr[L].push_back({R,i});
}
for(i=1;i<=4*n;i++)
{
arb[i].L=arb[i].R=arb[i].LR=-(1<<29);
}
for(i=n;i>=1;i--)
{
update(1,1,n,i,v[i],1);
for(auto it: l[i])
update(1,1,n,it.first,it.second,0);
for(auto it: qr[i])
an[it.second]=Q(i,it.first);
}
for(i=1;i<=q;i++)
cout<<an[i]<<'\n';
return 0;
}
