#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int mxn=5e5+5;
int a[mxn];
struct node{
int mx,mxf,mxa;
node operator+(node b){
node rs;
rs.mx=max({mx,b.mx,mxf+b.mxa});
rs.mxf=max(mxf,b.mxf);
rs.mxa=max(mxa,b.mxa);
return rs;
}
}t[4*mxn];
void build(int i,int l,int r){
if(l==r)return void(t[i]={0,0,a[l]});
int m=(l+r)>>1;build(2*i,l,m);build(2*i+1,m+1,r);
t[i]=t[2*i]+t[2*i+1];
}
void update(int i,int l,int r,int idx,int v){
if(r<idx||l>idx)return;
if(l==r){
t[i].mxf=max(t[i].mxf,v);
t[i].mx=t[i].mxf+t[i].mxa;
return;
}int m=(l+r)>>1;update(2*i,l,m,idx,v);update(2*i+1,m+1,r,idx,v);
t[i]=t[2*i]+t[2*i+1];
}
node query(int i,int l,int r,int tl,int tr){
if(r<tl||l>tr)return {0,0,0};
if(r<=tr&&l>=tl)return t[i];
int m=(l+r)>>1;
return query(2*i,l,m,tl,tr)+query(2*i+1,m+1,r,tl,tr);
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
stack<int>st;vector<pii>gd;
for(int i=1;i<=n;i++){
while(!st.empty()&&a[st.top()]<=a[i])gd.pb({st.top(),i}),st.pop();
if(!st.empty())gd.pb({st.top(),i});st.push(i);
}int id=0;build(1,1,n);
int q;cin>>q;int ans[q+1];
vector<pii>qr[n+1];
for(int i=1;i<=q;i++){
int l,r;cin>>l>>r;
qr[l].pb({r,i});
}sort(gd.rbegin(),gd.rend());
for(int l=n;l>=1;l--){
while(id<gd.size()&&gd[id].f>=l){id++;
int idx=gd[id-1].s*2-gd[id-1].f;
if(idx>n){continue;}
update(1,1,n,idx,a[gd[id-1].f]+a[gd[id-1].s]);
}
for(auto it : qr[l]){
ans[it.s]=query(1,1,n,l,it.f).mx;
}
}for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
}
