#include<bits/stdc++.h>
using namespace std;
//Let's do sub case 2 first
struct segmentTree
{
vector<int> val;
segmentTree(int n)
{
for(int i=0;i<2*n;i++)
val.push_back(0);
}
void update(int idx, int v)
{
idx = idx + (val.size())/2 - 1;
val[idx] = v;
idx /= 2;
while(idx != 0)
{
val[idx] = max(val[2*idx],val[2*idx+1]);
idx /= 2;
}
}
int ans(int idx, int tl, int tr, int l, int r)
{
if(l > tr || r < tl)
return 0;
if(l <= tl && r >= tr)
return val[idx];
int can1 = ans(2*idx,tl,(tl+tr)/2,l,r);
int can2 = ans(2*idx+1,(tl+tr)/2 +1,tr,l,r);
//cout<<"ACCESS: "<<idx<<' '<<tl<<' '<<tr<<' '<<l<<' '<<r<<' '<<max(can1,can2)<<endl;
return max(can1,can2);
}
};
const int N = 8192;
int dp[N][N];
int v[N];
bool found[N][N];
segmentTree tree = segmentTree(N);
void DP(int l, int r)
{
found[l-1][r-1] = true;
if(r - l < 2)
return;
if(!found[l][r-1])
DP(l+1,r);
if(!found[l-1][r-2])
DP(l,r-1);
dp[l-1][r-1] = max(max(dp[l][r-1],dp[l-1][r-2]),v[l-1]+v[r-1]+tree.ans(1,1,8192,l+1,(l+r)/2));
}
int main()
{
int n;
cin>>n;
if(n > N)
return 0;
for(int i=0;i<n;i++)
{
int a;
cin>>a;
tree.update(i+1,a);
v[i] = a;
}
DP(1,n);
int q;
cin>>q;
for(int i=0;i<q;i++)
{
int l,r;
cin>>l>>r;
if(!found[l-1][r-1])
DP(l,r);
cout<<dp[l-1][r-1]<<endl;
}
return 0;
}
