#include<bits/stdc++.h>
using namespace std;
#define task "text"
#define fi first
#define se second
using ll = long long;
const int N = 5e5+5;
ll a[N],ans[N];
vector<pair<int,int>> query[N];
vector<int> conn[N];
int n,q;
struct segtree{
ll maxa[4*N],st[4*N],lz[4*N];
int n;
void build(int id,int l,int r){
if(l==r){
maxa[id]=a[l];
st[id]=a[l];
return;
}
int mid=(l+r)>>1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
maxa[id]=max(maxa[id<<1],maxa[id<<1|1]);
st[id]=maxa[id];
}
void down(int id,int l,int r){
if(lz[id] == 0) return;
ll t=lz[id];
lz[id<<1]=max(lz[id<<1],t);
lz[id<<1|1]=max(lz[id<<1|1],t);
st[id<<1]=max(st[id<<1],maxa[id<<1]+lz[id<<1]);
st[id<<1|1]=max(st[id<<1|1],maxa[id<<1|1]+lz[id<<1|1]);
lz[id]=0;
return;
}
void update(int id,int l,int r,int u,int v,ll val){
if(r<u || v<l) return;
if(u<=l && r<=v){
lz[id]=max(lz[id],val);
st[id]=max(st[id],lz[id]+maxa[id]);
return;
}
int mid=(l+r)>>1;
down(id,l,r);
update(id<<1,l,mid,u,v,val);
update(id<<1|1,mid+1,r,u,v,val);
st[id]=max({st[id],st[id<<1],st[id<<1|1]});
}
ll get(int id,int l,int r,int u,int v){
if(r<u || v<l) return 0;
if(u<=l && r<=v) return st[id];
int mid=(l+r)>>1;
down(id,l,r);
return max(get(id<<1,l,mid,u,v),get(id<<1|1,mid+1,r,u,v));
}
}st;
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
if(fopen(task".INP","r")){
freopen(task".INP","r",stdin);
//freopen(task".OUT","w",stdout);
}
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
st.build(1,1,n);
cin>>q;
for(int i=1;i<=q;i++){
int l,r;
cin>>l>>r;
query[l].push_back({r,i});
}
vector<int> stk;
for(int i=1;i<=n;i++){
while(!stk.empty() && a[stk.back()] < a[i]) stk.pop_back();
if(!stk.empty()){
conn[stk.back()].push_back(i);
}
stk.push_back(i);
}
stk.clear();
for(int i=n;i>=1;i--){
while(!stk.empty() && a[stk.back()] < a[i]) stk.pop_back();
if(!stk.empty()){
conn[i].push_back(stk.back());
}
stk.push_back(i);
}
stk.clear();
for(int i=n;i>=1;i--){
for(int j:conn[i]){
int nxt=j+j-i;
if(nxt <= n){
st.update(1,1,n,nxt,n,a[i]+a[j]);
}
}
for(auto &[r,id]:query[i]){
ans[id]=st.get(1,1,n,i+2,r);
}
}
for(int i=1;i<=q;i++){
cout<<ans[i]<<'\n';
}
}
