#include <bits/stdc++.h>
//#define int long long
const int N=500010;
const int mul = 4;
int arr[N];
int ans[N];
std::vector<std::pair<int,int>> query[N];
std::vector<int> bPair[N];
class Segtree{
int seg[N*mul],Cv[N*mul],Lz[N*mul];
public:
void build(int c,int l,int r){
if(l==r){
Cv[c]=arr[l];//c value const
seg[c]=-1e9;//a+b value
}
int mid=(l+r)/2;
build(c*2,l,mid);
build(c*2+1,mid+1,r);
Cv[c]=std::max(Cv[c*2],Cv[c*2+1]);
}
void push(int c){
if(c*2<N*mul)Lz[c*2]=std::max(Lz[c*2],Lz[c]);
if(c*2+1<N*mul)Lz[c*2+1]=std::max(Lz[c*2+1],Lz[c]);
seg[c]=std::max(seg[c],Lz[c]);
Lz[c]=-1e9;
}
void update(int c,int l,int r,int ql,int qr,int v){
push(c);
if(ql<=l&&r<=qr){
Lz[c]=v;
}
if(qr<l||ql>r)return;
int mid = (l+r)/2;
update(c*2,l,mid,ql,qr,v);
update(c*2+1,mid+1,r,ql,qr,v);
}
int get(int c,int l,int r,int ql,int qr){
push(c);
if(ql<=l&&r<=qr){
return Cv[c]+seg[c];
}
if(qr<l||ql>r)return -1e9;
int mid = (l+r)/2;
return std::max(get(c,l,mid,ql,qr),get(c,mid+1,r,ql,qr));
}
};
signed main(){
int n,q;
std::cin >> n;
for(int i=1;i<=n;i++)std::cin >> arr[i];
std::cin >> q;
for(int i=1;i<=q;i++){
int l,r;
std::cin >> l >> r;
query[l].push_back({r,i});
}
std::stack<int> stk;
for(int i=1;i<=n;i++){
while(!stk.empty()&&arr[stk.top()]<arr[i])stk.pop();
if(!stk.empty())bPair[stk.top()].push_back(i);
stk.push(i);
}
while(!stk.empty())stk.pop();
for(int i=n;i>=1;i--){
while(!stk.empty()&&arr[stk.top()]<arr[i])stk.pop();
if(!stk.empty())bPair[i].push_back(stk.top());
stk.push(i);
}
Segtree st;
st.build(1,1,n);
for(int i=n;i>=1;i--){
for(auto r:bPair[i]){
int cMP = r+(r-i);
st.update(1,1,N,cMP,N,arr[i]+arr[r]);
}
for(auto [r,ai]:query[i]){
ans[ai]=st.get(1,1,N,i,r);
}
}
for(int i=1;i<=q;i++){
std::cout << ans[i] << '\n';
}
}
