#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
typedef pair<int,int>i2;
long long c,d,x,y,z,n,q;
int i,j,k;
long long ans[N],a[N];
vector<i2>b[N];
vector<int>g[N];
deque<int>dq;
struct gv
{
long long l,r,val;
};
gv st[4*N];
gv combine(gv x,gv y)
{
gv c={0,0,0};
c.l=max(x.l,y.l);
c.r=max(x.r,y.r);
c.val=max({x.val,y.val,x.l+y.r});
return c;
}
void buildtree(int id,int l,int r)
{
if (l==r)
{
st[id].l=0;
st[id].r=a[l];
st[id].val=a[l];
return;
}
int mid=(l+r)/2;
buildtree(id*2,l,mid);
buildtree(id*2+1,mid+1,r);
st[id]=combine(st[id*2],st[id*2+1]);
}
void update(int id,int l,int r,int i,long long val)
{
if (i<l || r<i) return;
if (l==r)
{
st[id].l=max(st[id].l,val);
st[id].val=max({st[id].val,st[id].l+st[id].r});
return;
}
int mid=(l+r)/2;
update(id*2,l,mid,i,val);
update(id*2+1,mid+1,r,i,val);
st[id]=combine(st[id*2],st[id*2+1]);
}
gv get(int id,int l,int r,int u,int v)
{
if (v<l || r<u) return {0,0,0};
if (u<=l && r<=v) return st[id];
int mid=(l+r)/2;
return combine(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for (int i=1;i<=n;i++)
cin>>a[i];
for (int i=n;i>=1;i--)
{
while (dq.size() && a[dq.back()]<a[i])
{
g[i].push_back(dq.back());
dq.pop_back();
}
if (dq.size()) g[i].push_back(dq.back());
dq.push_back(i);
}
buildtree(1,1,n);
cin>>q;
for (int i=1;i<=q;i++)
{
cin>>x>>y;
b[x].push_back({i,y});
}
for (int i=n;i>=1;i--)
{
for (int j=0;j<g[i].size();j++)
{
y=g[i][j]; x=i;
update(1,1,n,2*y-x,a[x]+a[y]);
}
for (int j=0;j<b[i].size();j++)
{
z=b[i][j].first; x=i; y=b[i][j].second;
gv c=get(1,1,n,x,y);
ans[z]=c.val;
}
}
for (int i=1;i<=q;i++)
cout<<ans[i]<<"\n";
}
