#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define x first
#define y second
struct st
{
vector<ll> cad;
ll query(ll a, ll b)
{
ll s=0;
a+=cad.size()/2;
b+=cad.size()/2;
while(a<=b)
{
if(a%2==1)s=max(s,cad[a++]);
if(b%2==0)s=max(s,cad[b--]);
a/=2;
b/=2;
}
return s;
}
void update(ll a, ll b)
{
a+=cad.size()/2;
cad[a]=b;
a/=2;
while(a>0)
{
cad[a]=max(cad[a*2],cad[a*2+1]);
a/=2;
}
}
st(ll n)
{
cad.resize(n*4);
}
};
int main()
{
ll n;
cin>>n;
st asd(n+2);
vector<ll> cad(n+1);
for(int i=1; i<=n; i++)
{
cin>>cad[i];
asd.update(i,cad[i]);
}
cad[0]=1e10;
vector<pair<ll,ll>> p;
stack<ll> q;q.push(0);
for(int i=1; i<=n; i++)
{
while(cad[q.top()]<=cad[i])
{
p.push_back({q.top(),i});
q.pop();
}
p.push_back({q.top(),i});
q.push(i);
}
ll qu;
cin>>qu;
while(qu--)
{
ll a, b,ans=0;
cin>>a>>b;
for(auto i:p)
{
if(a<=i.x&&i.y*2-i.x<=b)
ans=max(ans,cad[i.x]+cad[i.y]+asd.query(i.y*2-i.x,b));
}
cout<<ans<<"\n";
}
}
