#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 queries
{
int L,R,ID;
} Q[N];
bool cmp(queries a,queries b)
{
return a.L<b.L;
}
int n,S,request,a[N],ma_S[N],f[N],lazy_S[N],l,x,y,z,u,v; ll best,ans[N],res_S[N]; deque <int> dq;
vector <pii> ve;
int main()
{
ios_base::sync_with_stdio(NULL);
cin.tie(NULL); cout.tie(NULL);
cin >> n;
S=trunc(sqrt(n));
for (int i=1;i<=n;i++)
{
cin >> a[i];
ma_S[i/S]=max(ma_S[i/S],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);
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--;
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];
x=2*y-x;
u=(x+S-1)/S;
y=u*S-1;
v=(n-S+1)/S;
for (int j=x;j<=y;j++)
{
if (f[j]>=z) break;
f[j]=z;
res_S[j/S]=max(res_S[j/S],(ll) f[j]+a[j]);
}
for (int j=u;j<=v;j++)
{
if (lazy_S[j]>=z) break;
lazy_S[j]=z;
res_S[j]=max(res_S[j],(ll) lazy_S[j]+ma_S[j]);
}
x=(v+1)*S;
for (int j=x;j<=n;j++)
{
if (f[j]>=z) break;
f[j]=z;
res_S[j/S]=max(res_S[j/S],(ll) f[j]+a[j]);
}
l--;
}
x=Q[i].L+2;
y=Q[i].R;
u=(x+S-1)/S;
v=(y/S+1)/S;
y=u*S-1;
best=0;
for (int j=x;j<=y;j++)
best=max(best,(ll) max(f[j],lazy_S[j/S])+a[j]);
for (int j=u;j<=v;j++)
best=max(best,res_S[j]);
x=(v+1)*S;
y=Q[i].R;
for (int j=x;j<=y;j++)
best=max(best,(ll) max(f[j],lazy_S[j/S])+a[j]);
ans[Q[i].ID]=best;
}
for (int i=1;i<=request;i++)
cout << ans[i] << '\n';
}
