#include <bits/stdc++.h>
#define int long long
const int N=5010;
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){
//std::cout << c << ' ' << l << ' '<< r <<'\n';
if(l==r){
Cv[c]=arr[l];//c value const
return;
}
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]);
seg[c]=Cv[c];
}
void push(int c){
if(c*2<N*mul)Lz[c*2]=std::max(Lz[c*2],Lz[c]),seg[c*2]=std::max(seg[c*2],Cv[c*2]+Lz[c*2]);
if(c*2+1<N*mul)Lz[c*2+1]=std::max(Lz[c*2+1],Lz[c]),seg[c*2+1]=std::max(seg[c*2+1],Cv[c*2+1]+Lz[c*2+1]);
seg[c]=std::max(seg[c],Cv[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;
seg[c]=std::max(seg[c],Cv[c]+Lz[c]);
return;
}
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);
seg[c]=std::max(seg[c],seg[c*2+1]);
seg[c]=std::max(seg[c],seg[c*2]);
}
int get(int c,int l,int r,int ql,int qr){
push(c);
if(ql<=l&&r<=qr){
//std::cout << c << ' ' << l << ' ' << r << ' ' << Cv[c] << ' ' << seg[c] << '\n';
return seg[c];
}
if(qr<l||ql>r)return -1e9;
int mid = (l+r)/2;
return std::max(get(c*2,l,mid,ql,qr),get(c*2+1,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);
if(cMP<=n)st.update(1,1,n,cMP,n,arr[i]+arr[r]);
//std::cout << '(' << i << ',' << r << ')' << "->" << cMP << '\n';
}
for(auto [r,ai]:query[i]){
ans[ai]=st.get(1,1,n,i+2,r);
//std::cout << ai << ' ' << i << ' ' << r << ' ' << ans[ai];
}
}
for(int i=1;i<=q;i++){
std::cout << ans[i] << '\n';
}
}
/*
5
5 2 1 5 3
3
1 4
2 5
1 5
*/
