#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll MOD=1e9+7;
const ll N=1e6+5;
const ld pi=3.14159265359;
const ll INF=(1LL<<62);
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()
ll seg[4*N],tag[4*N],n,u[N],m,lst,ans[N],pseg[4*N];
vector<pll> upd[N];
pair<pll,ll> q[N];
stack<pll> stk;
void push(ll id){
tag[id*2]=max(tag[id*2],tag[id]);
tag[id*2+1]=max(tag[id*2+1],tag[id]);
seg[id*2]=max(seg[id*2],pseg[id*2]+tag[id*2]);seg[id*2+1]=max(seg[id*2+1],pseg[id*2+1]+tag[id*2+1]);
}
void add(ll id,ll l,ll r,ll ql,ll qr,ll D){
if(l>=ql&&r<=qr){
tag[id]=max(tag[id],D);
push(id);
seg[id]=max(seg[id*2],seg[id*2+1]);
seg[id]=max(seg[id],pseg[id]+tag[id]);
//cout<<id<<" "<<l<<" "<<r<<" "<<seg[id]<<"\n";
return ;
}
if(l>=qr||r<=ql)return ;
push(id);
ll mid=(l+r)/2;
add(id*2,l,mid,ql,qr,D);
add(id*2+1,mid,r,ql,qr,D);
seg[id]=max(seg[id*2],seg[id*2+1]);
//cout<<id<<" "<<l<<" "<<r<<" "<<seg[id]<<"\n";
}
void pins(ll id,ll l,ll r,ll to,ll D){
if(l==r-1){pseg[id]=max(pseg[id],D);return ;}
ll mid=(l+r)/2;
if(to<mid){
pins(id*2,l,mid,to,D);
}else{
pins(id*2+1,mid,r,to,D);
}
pseg[id]=max(pseg[id*2],pseg[id*2+1]);
}
ll Q(ll id,ll l,ll r,ll ql,ll qr){
//cout<<id<<" "<<l<<" "<<r<<" "<<seg[id]<<"\n";
if(l>=ql&&r<=qr)return seg[id];
if(l>=qr||r<=ql)return 0;
push(id);
ll mid=(l+r)/2;
return max(Q(id*2,l,mid,ql,qr),Q(id*2+1,mid,r,ql,qr));
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n;
lst=n;
REP1(i,n)cin>>u[i],pins(1,1,n+1,i,u[i]);
REP1(i,n){
while(SZ(stk)&&stk.top().X<=u[i]){
upd[stk.top().Y].pb(mp(i,stk.top().X+u[i]));
stk.pop();
}
if(SZ(stk)){upd[stk.top().Y].pb(mp(i,stk.top().X+u[i]));}
stk.push(mp(u[i],i));
}
cin>>m;
REP(i,m)cin>>q[i].X.X>>q[i].X.Y,q[i].Y=i;
sort(q,q+m,[](pair<pll,ll> A,pair<pll,ll> B){
return (A.X.X>B.X.X);
});
REP(i,m){
//cout<<"que : "<<q[i].X.X<<" "<<q[i].X.Y<<"\n";
while(lst>=q[i].X.X){
for(auto j:upd[lst]){
if(j.X+j.X-lst>=n+1)continue;
//cout<<"upd : "<<j.X<<" "<<2*j.X-lst<<" "<<j.Y<<"\n";
add(1,1,n+1,2*j.X-lst,n+1,j.Y);
}
--lst;
}
ans[q[i].Y]=Q(1,1,n+1,q[i].X.X+2,q[i].X.Y+1);
}
REP(i,m)cout<<ans[i]<<"\n";
return 0;
}
/*
5
5 2 1 5 3
3
1 5
2 5
1 4
*/
