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