#include <bits/stdc++.h>
#define Tree int h,int l,int r
#define Left (h<<1),l,(l+r)>>1
#define Right ((h<<1)|1),((l+r)>>1)+1,r
#define F first
#define S second
using namespace std;
const int N=5e5+5;
int n,q;
int a[N],ans[N];
deque < int > dq;
vector < pair < int , int > > Q[N],E[N];
typedef struct { int li; int r; int ans; } node;
node v[4*N];
void B(int h) {
v[h].ans=max(v[h].ans,v[h].li+v[h].r);
return ;
}
void Shift(Tree) {
v[(h<<1)].li=max(v[(h<<1)].li,v[h].li);
v[((h<<1)|1)].li=max(v[((h<<1)|1)].li,v[h].li);
B((h<<1)),B(((h<<1)|1));
}
void Upd(Tree,int L,int R,int vl) {
if (r<L || R<l) return ;
if (L<=l && r<=R) {
v[h].li=max(v[h].li,vl);
B(h);
return ;
}
Shift(h,l,r);
Upd(Left,L,R,vl);
Upd(Right,L,R,vl);
v[h].ans=max(v[(h<<1)].ans,v[((h<<1)|1)].ans);
}
int L,R;
int get(Tree) {
if (r<L || R<l) return 0;
if (L<=l && r<=R) return v[h].ans;
Shift(h,l,r);
int x=get(Left);
int y=get(Right);
return max(x,y);
}
void Build(Tree) {
if (l==r) {
v[h].r=a[r];
return ;
}
Build(Left);
Build(Right);
v[h].r=max(v[(h<<1)].r,v[((h<<1)|1)].r);
}
main () {
ios::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
cin>>n;
a[0]=1e8+1;
for (int i=1; i<=n; i++) {
cin>>a[i];
}
dq.push_back(0);
for (int l,i=1,r; i<=n; i++) {
while (a[dq.back()]<a[i])
dq.pop_back();
l=dq.back();
if (l) {
r=i+i-l;
if (r<=n)
E[l].push_back({r,a[l]+a[i]});
}
dq.push_back(i);
}
while (dq.size()) dq.pop_back();
dq.push_back(0);
for (int l=n,i,r; l>=1; l--) {
while (a[dq.back()]<a[l])
dq.pop_back();
i=dq.back();
if (i) {
r=i+i-l;
if (r<=n)
E[l].push_back({r,a[l]+a[i]});
}
dq.push_back(l);
}
Build(1,1,n);
cin>>q;
for (int i=1; i<=q; i++) {
int l,r;
cin>>l>>r;
Q[l].push_back({r,i});
}
for (L=n; L>=1; --L) {
for (int j=0; j<E[L].size(); j++) {
Upd(1,1,n,E[L][j].F,n,E[L][j].S);
}
for (int j=0; j<Q[L].size(); j++) {
int id=Q[L][j].S;
R=Q[L][j].F;
ans[id]=get(1,1,n);
}
}
for (int i=1; i<=q; i++)
cout<<ans[i]<<"\n";
}
