#include <bits/stdc++.h>
using namespace std;
const int INF = 4e8;
int n;
int a[500005];
int tole[500005],tori[500005];
vector<pair<pair<int,int>,int>> intervals;
vector<pair<int,int>> withle[500005];
void calc_toletori()
{
deque<int> dq;
for(int i=1;i<=n;i++)
{
while(!dq.empty() && a[i] > a[dq.back()])
dq.pop_back();
if(dq.empty())
tole[i] = 0;
else
tole[i] = dq.back();
dq.push_back(i);
}
dq.clear();
for(int i=n;i>0;i--)
{
while(!dq.empty() && a[i] > a[dq.back()])
dq.pop_back();
if(dq.empty())
tori[i] = n+1;
else
tori[i] = dq.back();
dq.push_back(i);
}
}
void get_intervals()
{
for(int c=1;c<=n;c++)
{
int st = tole[c];
if(st==0)
continue;
intervals.push_back({{st, c + (c-st)}, a[c]+a[st]});
}
for(int st=1;st<=n;st++)
{
int c = tori[st];
if(c==n+1)
continue;
intervals.push_back({{st, c + (c-st)}, a[c]+a[st]});
}
}
vector<pair<int,int>> qrys[500005];
int rez[500005];
int max_init[1100000],max_now[1100000],max_justnow[1100000],lazy[1100000];
void build(int nod, int st, int dr)
{
max_now[nod] = max_justnow[nod] = -INF;
if(st==dr)
{
max_init[nod] = a[st];
return;
}
int mij=(st+dr)/2;
build(nod*2,st,mij);
build(nod*2+1,mij+1,dr);
max_init[nod] = max(max_init[nod*2], max_init[nod*2+1]);
}
void apply(int nod, int lazy_val)
{
lazy[nod] = lazy_val;
max_now[nod] = max_init[nod] + lazy_val;
max_justnow[nod] = lazy_val;
}
void propagate(int nod)
{
if(!lazy[nod])
return;
apply(nod*2,lazy[nod]);
apply(nod*2+1,lazy[nod]);
lazy[nod] = 0;
}
void upd_assign(int nod, int st, int dr, int le, int ri, int newv)
{
if(le>ri)
return;
if(le==st && dr==ri)
{
apply(nod,newv);
return;
}
propagate(nod);
int mij=(st+dr)/2;
upd_assign(nod*2,st,mij,le,min(mij,ri),newv);
upd_assign(nod*2+1,mij+1,dr,max(mij+1,le),ri,newv);
max_now[nod] = max(max_now[nod*2], max_now[nod*2+1]);
max_justnow[nod] = max(max_justnow[nod*2], max_justnow[nod*2+1]);
}
int qry(int nod, int st, int dr, int le, int ri)
{
if(le>ri)
return -INF;
if(le==st && dr==ri)
return max_now[nod];
propagate(nod);
int mij=(st+dr)/2;
return max(qry(nod*2,st,mij,le,min(mij,ri)), qry(nod*2+1,mij+1,dr,max(mij+1,le),ri));
}
int cautare_binara(int nod, int st, int dr, int newv)
{
if(st==dr)
{
if(max_justnow[nod] < newv)
return n+1;
return st;
}
propagate(nod);
int mij=(st+dr)/2;
if(max_justnow[nod*2] < newv)
return cautare_binara(nod*2+1,mij+1,dr,newv);
else
return cautare_binara(nod*2,st,mij,newv);
}
void update(int le, int newv)
{
int ri = cautare_binara(1,1,n,newv);
upd_assign(1,1,n,le,ri-1,newv);
}
int query(int ri)
{
return qry(1,1,n,1,ri);
}
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
calc_toletori();
get_intervals();
for(auto [x,val]:intervals)
withle[x.first].push_back({x.second,val});
int q;
cin>>q;
for(int i=0;i<q;i++)
{
int le,ri;
cin>>le>>ri;
qrys[le].push_back({ri,i});
}
build(1,1,n);
for(int le=n;le>=1;le--)
{
for(auto [ri,val]:withle[le])
{
update(ri,val);
}
for(auto [ri,id]:qrys[le])
{
rez[id] = query(ri);
}
}
for(int i=0;i<q;i++)
cout<<rez[i]<<"\n";
return 0;
}
/*
5
5 2 1 5 3
3
1 4
2 5
1 5
tori[i] = prima pozitie x din dreapta lui i cu a[x] >= a[i]
tole[i] = prima pozitie x din stanga lui i cu a[x] >= a[i]
daca ne fixam capatu stanga in le, centru o sa fie in intervalu le+1..tori[le]
daca ne fixam centru in c, capatu stanga o sa fie in tole[c]..c-1
*/
