#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
int L[MAXN],R[MAXN],A[MAXN],ans[MAXN],seg[MAXN*4],lazy[MAXN*4],F[MAXN*4];
vector<int> vi[MAXN];
vector< pair<int,int> > vq[MAXN];
void build(int l,int r,int pos)
{
if(l==r)
{
F[pos]=seg[pos]=A[l];
return ;
}
int mid=(l+r)/2;
build(l,mid,pos*2);
build(mid+1,r,pos*2+1);
F[pos]=seg[pos]=max(F[pos*2],F[pos*2+1]);
}
void down(int pos)
{
int val=lazy[pos];
seg[pos*2]=max(seg[pos*2],val+F[pos*2]);
seg[pos*2+1]=max(seg[pos*2+1],val+F[pos*2+1]);
lazy[pos*2]=max(lazy[pos*2],val);
lazy[pos*2+1]=max(lazy[pos*2+1],val);
lazy[pos]=0;
}
void update(int l,int r,int u,int v,int val,int pos)
{
if(v<l||r<u) return ;
if(u<=l&&r<=v)
{
seg[pos]=max(seg[pos],val+F[pos]);
lazy[pos]=max(lazy[pos],val);
return ;
}
int mid=(l+r)/2;
down(pos);
update(l,mid,u,v,val,pos*2);
update(mid+1,r,u,v,val,pos*2+1);
seg[pos]=max(seg[pos*2],seg[pos*2+1]);
}
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;
down(pos);
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);
return max(get(l,mid,u,v,pos*2),get(mid+1,r,u,v,pos*2+1));
}
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];
stack<int> st;
for(int i=1;i<=n;i++)
{
while(!st.empty()&&A[i]>A[st.top()]) st.pop();
if(st.empty()) L[i]=-1;
else L[i]=st.top();
st.push(i);
}
while(!st.empty()) st.pop();
for(int i=n;i;i--)
{
while(!st.empty()&&A[i]>=A[st.top()]) st.pop();
if(st.empty()) R[i]=-1;
else R[i]=st.top();
st.push(i);
}
for(int i=1;i<=n;i++)
{
if(L[i]!=-1) vi[L[i]].push_back(i);
if(R[i]!=-1) vi[i].push_back(R[i]);
}
build(1,n,1);
cin>>q;
for(int i=1;i<=q;i++)
{
int l,r;
cin>>l>>r;
vq[l].push_back({r,i});
}
for(int i=n;i;i--)
{
for(auto v:vi[i]) update(1,n,v*2-i,n,A[i]+A[v],1);
for(auto v:vq[i]) ans[v.second]=get(1,n,i,v.first,1);
}
for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
}
