#include<bits/stdc++.h>
#define int long long
using namespace std;
int ar[500005];
vector<pair<int,int>>qr[500005];
vector<pair<int,int>>add[500005];
int ans[500005];
struct node{
int ans,mx;
node(int a=0,int b=0){
mx=a,ans=b;
}
friend node operator+(node a,node b){
return node(max(a.mx,b.mx),max(a.ans,b.ans));
}
};
struct segtree{
node info[2000005];
int lz[2000005];
void build(int st,int en,int i){
if(st==en){
info[i]=node(ar[st],0);
return;
}
int m=(st+en)/2;
build(st,m,i*2);
build(m+1,en,i*2+1);
info[i]=info[i*2]+info[i*2+1];
}
void push(int st,int en,int i){
if(lz[i]==0)return;
info[i].ans=max(info[i].ans,info[i].mx+lz[i]);
if(st!=en){
lz[i*2]=max(lz[i],lz[i*2]);
lz[i*2+1]=max(lz[i*2+1],lz[i]);
}
lz[i]=0;
}
void upd(int st,int en,int i,int l,int r,int val){
push(st,en,i);
if(st>r||en<l)return;
if(st>=l&&en<=r){
lz[i]=val,push(st,en,i);
//cerr<<"upd:"<<st<<" "<<en<<" "<<info[i].ans<<' '<<info[i].mx<<"\n";
return;
}
int m=(st+en)/2;
upd(st,m,i*2,l,r,val);
upd(m+1,en,i*2+1,l,r,val);
info[i]=info[i*2]+info[i*2+1];
}
node fans(int st,int en,int i,int l,int r){
push(st,en,i);
if(st>r||en<l)return node();
if(st>=l&&en<=r)return info[i];
int m=(st+en)/2;
return fans(st,m,i*2,l,r)+fans(m+1,en,i*2+1,l,r);
}
}tr;
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>ar[i];
stack<int>s;
for(int i=n;i>=1;i--){
while(!s.empty()&&ar[i]>ar[s.top()]){
//cerr<<i<<' '<<s.top()<<' '<<2*s.top()-i<<"\n";
add[i].push_back({ar[i]+ar[s.top()],2*s.top()-i});
s.pop();
}
if(!s.empty()){
add[i].push_back({ar[i]+ar[s.top()],2*s.top()-i});
//cerr<<i<<' '<<s.top()<<' '<<2*s.top()-i<<"\n";
}
s.push(i);
}
tr.build(1,n,1);
int q;cin>>q;
for(int i=0;i<q;i++){
int l,r;cin>>l>>r;
qr[l].push_back({r,i});
}
for(int i=n;i>=1;i--){
//cerr<<"i:"<<i<<"\n";
for(auto x:add[i]){
tr.upd(1,n,1,x.second,n,x.first);
//cerr<<x.second<<" "<<x.first<<"\n";
}
for(auto [x,id]:qr[i]){
ans[id]=tr.fans(1,n,1,i,x).ans;
}
}
for(int i=0;i<q;i++)cout<<ans[i]<<"\n";
}
