#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define X first
#define Y second
const int N=5e5+5;
struct query
{
int L,R,ID;
} Q[N];
bool cmp(query a,query b)
{
return a.L<b.L;
}
int n,request,l,x,y,z,u,v,a[N],ori_t[4*N],lazy[4*N]; ll t[4*N],ans[N];
vector <pii> ve; deque <int> dq;
void down(int id)
{
lazy[id*2]=max(lazy[id*2],lazy[id]);
lazy[id*2+1]=max(lazy[id*2+1],lazy[id]);
t[id*2]=max(t[id*2],(ll)ori_t[id*2]+lazy[id*2]);
t[id*2+1]=max(t[id*2+1],(ll)ori_t[id*2+1]+lazy[id*2+1]);
}
void build(int id,int l,int r)
{
if (l==r)
{
ori_t[id]=a[l];
return;
}
int m=(l+r)/2;
build(id*2,l,m);
build(id*2+1,m+1,r);
ori_t[id]=max(ori_t[id*2],ori_t[id*2+1]);
}
void update(int id,int l,int r)
{
if (u>r or v<l) return;
if (u<=l and v>=r)
{
lazy[id]=max(lazy[id],z);
t[id]=max(t[id],(ll)ori_t[id]+lazy[id]);
return;
}
down(id);
int m=(l+r)/2;
update(id*2,l,m);
update(id*2+1,m+1,r);
t[id]=max(t[id*2],t[id*2+1]);
}
ll get(int id,int l,int r)
{
if (u>r or v<l) return 0;
if (u<=l and v>=r) return t[id];
down(id);
int m=(l+r)/2;
return max(get(id*2,l,m),get(id*2+1,m+1,r));
}
int main()
{
ios_base::sync_with_stdio(NULL);
cin.tie(NULL); cout.tie(NULL);
cin >> n;
for (int i=1;i<=n;i++)
cin >> a[i];
cin >> request;
for (int i=1;i<=request;i++)
{
cin >> Q[i].L >> Q[i].R;
Q[i].ID=i;
}
sort(Q+1,Q+request+1,cmp);
ve.clear();
dq.clear();
for (int i=n;i>=1;i--)
{
while (!dq.empty() and a[i]>=a[dq.back()])
{
if (2*dq.back()-i<=n) ve.push_back(make_pair(i,dq.back()));
dq.pop_back();
}
if (!dq.empty() and 2*dq.back()-i<=n) ve.push_back(make_pair(i,dq.back()));
dq.push_back(i);
}
sort(ve.begin(),ve.end());
l=ve.size();
l--;
build(1,1,n);
for (int i=request;i>=1;i--)
{
while (l>=0 and ve[l].X>=Q[i].L)
{
x=ve[l].X;
y=ve[l].Y;
z=a[x]+a[y];
u=2*y-x;
v=n;
update(1,1,n);
l--;
}
u=Q[i].L+2;
v=Q[i].R;
ans[Q[i].ID]=get(1,1,n);
}
for (int i=1;i<=request;i++)
cout << ans[i] << '\n';
}
