//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
//#define endl '\n'
llo n;
llo it[500001];
vector<pair<llo,llo>> tt[500001];
llo tree[4*500001];
llo tree2[4*500001];
llo lazy[4*500001];
llo ans[500001];
void build(llo no,llo l,llo r){
if(l==r){
tree2[no]=it[l];
}
else{
llo mid=(l+r)/2;
build(no*2+1,l,mid);
build(no*2+2,mid+1,r);
tree2[no]=max(tree2[no*2+1],tree2[no*2+2]);
}
}
void push(llo no,llo l,llo r){
tree[no]=max(tree[no],tree2[no]+lazy[no]);
if(l<r){
lazy[no*2+1]=max(lazy[no*2+1],lazy[no]);
lazy[no*2+2]=max(lazy[no*2+2],lazy[no]);
}
lazy[no]=0;
}
void update(llo no,llo l,llo r,llo aa,llo bb,llo val){
push(no,l,r);
if(r<aa or l>bb){
return;
}
if(aa<=l and r<=bb){
tree[no]=max(tree[no],val+tree2[no]);
if(l<r){
lazy[no*2+1]=max(lazy[no*2+1],val);
lazy[no*2+2]=max(lazy[no*2+2],val);
}
}
else{
llo mid=(l+r)/2;
update(no*2+1,l,mid,aa,bb,val);
update(no*2+2,mid+1,r,aa,bb,val);
tree[no]=max(tree[no*2+1],tree[no*2+2]);
}
}
llo query(llo no,llo l,llo r,llo aa,llo bb){
push(no,l,r);
if(r<aa or l>bb){
return 0;
}
if(aa<=l and r<=bb){
return tree[no];
}
else{
llo mid=(l+r)/2;
return max(query(no*2+1,l,mid,aa,bb),query(no*2+2,mid+1,r,aa,bb));
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
for(llo i=0;i<n;i++){
cin>>it[i];
}
vector<pair<llo,llo>> ss;
for(llo i=0;i<n;i++){
while(ss.size()){
if(ss.back().a<it[i]){
ss.pop_back();
}
else{
break;
}
}
if(ss.size()){
llo ind=i-ss.back().b+i;
if(ind<n){
tt[ss.back().b].pb({i,-1});
//ans=max(ans,it[i]+ss.back().a+aa[ind]);
}
}
ss.pb({it[i],i});
}
ss.clear();
for(llo i=n-1;i>=0;i--){
while(ss.size()){
if(ss.back().a<it[i]){
ss.pop_back();
}
else{
break;
}
}
if(ss.size()){
llo ind=ss.back().b-i+ss.back().b;
if(ind<n){
tt[i].pb({ss.back().b,-1});
//ans=max(ans,it[i]+ss.back().a+aa[ind]);
}
}
ss.pb({it[i],i});
}
llo q;
cin>>q;
for(llo i=0;i<q;i++){
llo cc,dd;
cin>>cc>>dd;
cc--;
dd--;
tt[cc].pb({dd,i});
}
build(0,0,n-1);
for(llo i=n-1;i>=0;i--){
for(auto j:tt[i]){
//cout<<i<<":"<<j.a<<":"<<j.b<<endl;
if(j.b==-1){
llo ind=j.a+j.a-i;
//cout<<ind<<":"<<i<<","<<j.a<<":"<<it[j.a]+it[i]<<endl;
update(0,0,n-1,ind,n-1,it[j.a]+it[i]);
}
else{
ans[j.b]=query(0,0,n-1,i,j.a);
//cout<<j.b<<endl;
}
}
}
for(llo i=0;i<q;i++){
cout<<ans[i]<<'\n';
}
return 0;
}
