#include <bits/stdc++.h>
#define DIM 500010
#define INF 2000000000
using namespace std;
deque <int> d;
vector <int> events[DIM];
vector <pair<int,int> > qry[DIM];
int v[DIM],ans[DIM];
int n,i,q,x,y,sol;
struct segment_tree{
int maxi_init; /// maximul din sirul initial
int maxi;
int lazy;
} aint[DIM*4];
void build (int nod, int st, int dr){
aint[nod].maxi = -INF;
if (st == dr){
aint[nod].maxi_init = v[st];
return;
}
int mid = (st+dr)>>1;
build (nod<<1,st,mid);
build ((nod<<1)|1,mid+1,dr);
aint[nod].maxi_init = max (aint[nod<<1].maxi_init,aint[(nod<<1)|1].maxi_init);
}
void update_lazy (int nod, int st, int dr){
if (!aint[nod].lazy)
return;
if (st != dr){
int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
aint[fiu_st].lazy = max (aint[fiu_st].lazy,aint[nod].lazy);
aint[fiu_st].maxi = max (aint[fiu_st].maxi,aint[nod].lazy + aint[fiu_st].maxi_init);
aint[fiu_dr].lazy = max (aint[fiu_dr].lazy,aint[nod].lazy);
aint[fiu_dr].maxi = max (aint[fiu_dr].maxi,aint[nod].lazy + aint[fiu_dr].maxi_init);
}
aint[nod].lazy = 0;
}
void update (int nod, int st, int dr, int x, int y, int val){
update_lazy (nod,st,dr);
if (x <= st && dr <= y){
aint[nod].lazy = max (aint[nod].lazy,val);
aint[nod].maxi = max (aint[nod].maxi,val + aint[nod].maxi_init);
update_lazy(nod,st,dr);
return;
}
int mid = (st+dr)>>1;
if (x <= mid)
update (nod<<1,st,mid,x,y,val);
if (y > mid)
update ((nod<<1)|1,mid+1,dr,x,y,val);
update_lazy (nod<<1,st,mid);
update_lazy ((nod<<1)|1,mid+1,dr);
aint[nod].maxi = max (aint[nod<<1].maxi,aint[(nod<<1)|1].maxi);
}
void query (int nod, int st, int dr, int x, int y){
update_lazy (nod,st,dr);
if (x <= st && dr <= y){
sol = max (sol,aint[nod].maxi);
return;
}
int mid = (st+dr)>>1;
if (x <= mid)
query (nod<<1,st,mid,x,y);
if (y > mid)
query ((nod<<1)|1,mid+1,dr,x,y);
}
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n;
for (i=1;i<=n;i++)
cin>>v[i];
/// aflu perechile bune
for (i=1;i<=n;i++){
while (!d.empty() && v[i] >= v[d.back()]){
events[d.back()].push_back(i);
d.pop_back();
}
if (!d.empty())
events[d.back()].push_back(i);
d.push_back(i);
}
build (1,1,n);
cin>>q;
for (i=1;i<=q;i++){
cin>>x>>y;
qry[x].push_back(make_pair(y,i));
}
//for (i=1;i<=n;i++)
// for (auto it : events[i])
// cout<<i<<" "<<it<<"\n";
build (1,1,n);
for (i=n;i;i--){
for (auto it : events[i]){
int poz_b = it;
int poz_c = 2 * poz_b - i;
if (poz_c <= n)
update (1,1,n,poz_c,n,v[i]+v[poz_b]);
}
for (auto it : qry[i]){
sol = -INF;
query (1,1,n,i,it.first);
ans[it.second] = sol;
}
}
for (i=1;i<=q;i++)
cout<<ans[i]<<"\n";
return 0;
}
