#include<bits/stdc++.h>
using namespace std;
const int N=500005;
struct node{
int res,f,mx;
node(){res=f=mx=0;}
node(int _res,int _f,int _mx){
res=_res;
f=_f;
mx=_mx;
}
};
struct SegTree{
node tree[1<<20];
int sz;
node Merge(node&a,node&b){
int res=max({a.res,b.res,a.f+b.mx}),f=max(a.f,b.f),mx=max(a.mx,b.mx);
return node(res,f,mx);
}
void build(int l,int r,int p,vector<int>&a){
if(l==r){
tree[p].f=-1e9;
tree[p].res=-1e9;
tree[p].mx=0;
if(l<a.size())tree[p].mx=a[l];
return;
}
int md=(l+r)>>1;
build(l,md,p*2+1,a);
build(md+1,r,p*2+2,a);
tree[p]=Merge(tree[p*2+1],tree[p*2+2]);
}
void init(int n,vector<int>&a){
sz=1;
while(sz<n)sz*=2;
build(0,sz-1,0,a);
}
void update(int l,int r,int p,int idx,int f){
if(l==r){
tree[p].f=max(tree[p].f,f);
tree[p].res=tree[p].f+tree[p].mx;
return;
}
int md=(l+r)>>1;
if(md>=idx)update(l,md,p*2+1,idx,f);
else update(md+1,r,p*2+2,idx,f);
tree[p]=Merge(tree[p*2+1],tree[p*2+2]);
}
void update(int idx,int f){
update(0,sz-1,0,idx,f);
}
node query(int l,int r,int p,int l_q,int r_q){
if(l>r_q||r<l_q)return node(0,0,0);
if(l>=l_q&&r<=r_q)return tree[p];
int md=(l+r)>>1;
node ch1=query(l,md,p*2+1,l_q,r_q);
node ch2=query(md+1,r,p*2+2,l_q,r_q);
return Merge(ch1,ch2);
}
int query(int l,int r){
return query(0,sz-1,0,l,r).res;
}
}tree;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
vector<int>a(n);
for(int i=0;i<n;i++)cin>>a[i];
vector<pair<int,int>>seg;
vector<int>st;// decreasing stack
for(int i=0;i<n;i++){
while(!st.empty()&&a[i]>=a[st.back()]){
seg.push_back({st.back(),i});
st.pop_back();
}
if(!st.empty())seg.push_back({st.back(),i});
st.push_back(i);
}
sort(seg.begin(),seg.end());
tree.init(n,a);
int q;
cin>>q;
int L[q],R[q],sorted[q],ans[q];
for(int i=0;i<q;i++){
cin>>L[i]>>R[i];
L[i]--;R[i]--;
sorted[i]=i;
}
sort(sorted,sorted+q,[&](int i,int j){
return L[i]>L[j];
});
for(int i=0;i<q;i++){
while(!seg.empty()&&seg.back().first>=L[sorted[i]]){
auto[l,r]=seg.back();
if(2*r-l<n)tree.update(2*r-l,a[l]+a[r]);
seg.pop_back();
}
ans[sorted[i]]=tree.query(L[sorted[i]],R[sorted[i]]);
}
for(int i=0;i<q;i++)cout<<ans[i]<<"\n";
return 0;
}
