#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=500050;
const int M=2*N;
const int inf=1e9+7;
int a[N],ls[M],rs[M],tsz,root,mx1[M],mx2[M],lzy[M];
void Build(int &c, int ss, int se)
{
c=++tsz;mx2[c]=-inf;lzy[c]=-inf;
if(ss==se){ mx1[c]=a[ss];return;}
int mid=ss+se>>1;
Build(ls[c],ss,mid);
Build(rs[c],mid+1,se);
mx1[c]=max(mx1[ls[c]],mx1[rs[c]]);
}
void Upd(int c, int x)
{
mx2[c]=max(mx2[c],mx1[c]+x);
lzy[c]=max(lzy[c],x);
}
void Push(int c)
{
if(lzy[c]!=-inf)
{
Upd(ls[c],lzy[c]);
Upd(rs[c],lzy[c]);
lzy[c]=-inf;
}
}
void Set(int c, int ss, int se, int qs, int qe, int x)
{
if(qs>qe || qs>se || ss>qe) return;
if(qs<=ss && qe>=se){ Upd(c,x);return;}
Push(c);
int mid=ss+se>>1;
Set(ls[c],ss,mid,qs,qe,x);
Set(rs[c],mid+1,se,qs,qe,x);
mx2[c]=max(mx2[ls[c]],mx2[rs[c]]);
}
int Get(int c, int ss, int se, int qs, int qe)
{
if(qs>qe || qs>se || ss>qe) return -inf;
if(qs<=ss && qe>=se) return mx2[c];
Push(c);
int mid=ss+se>>1;
return max(Get(ls[c],ss,mid,qs,qe),Get(rs[c],mid+1,se,qs,qe));
}
int n,q,ans[N];
vector<pair<int,int>> Qs[N];
void Add(int x, int y)
{
int z=y+y-x;
//printf("%i %i %i\n",x,y,z);
Set(root,1,n,z,n,a[x]+a[y]);
}
void Solve()
{
stack<int> st;
for(int i=n;i>=1;i--)
{
while(st.size() && a[st.top()]<=a[i])
{
Add(i,st.top());
st.pop();
}
if(st.size()) Add(i,st.top());
st.push(i);
for(auto qu:Qs[i])
{
ans[qu.second]=Get(root,1,n,i,qu.first);
//printf("%i:(%i %i)\n",qu.second,i,qu.first);
}
}
//for(int i=1;i<=n;i++) printf("%i ",Get(root,1,n,i,i));printf("\n");
}
int main()
{
scanf("%i",&n);
for(int i=1;i<=n;i++) scanf("%i",&a[i]);
Build(root,1,n);
scanf("%i",&q);
for(int i=1;i<=q;i++)
{
int l,r;
scanf("%i %i",&l,&r);
Qs[l].pb({r,i});
}
Solve();
for(int i=1;i<=q;i++) printf("%i\n",ans[i]);
return 0;
}
