#include <bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N=5e5+5;
int mx[N*4],ans[N*4],add[N*4],a[N];
vector <pair <int,int> > qu[N];
vector <int> ab[N];
void build(int v,int tl,int tr){
if(tl==tr)mx[v]=a[tl];
else{
int tm=(tl+tr)/2;
build(v*2,tl,tm);
build(v*2+1,tm+1,tr);
mx[v]=max(mx[v*2],mx[v*2+1]);
}
}
void push(int v,int tl,int tr){
ans[v]=max(ans[v],add[v]+mx[v]);
if(tl!=tr){
add[v*2]=max(add[v*2],add[v]);
add[v*2+1]=max(add[v*2+1],add[v]);
}
add[v]=0;
}
void update(int v,int tl,int tr,int l,int r,int val){
if(add[v])push(v,tl,tr);
if(r<tl or tr<l)return;
if(l<=tl && tr<=r){
add[v]=val;
push(v,tl,tr);
return;
}
int tm=(tl+tr)/2;
update(v*2,tl,tm,l,r,val);
update(v*2+1,tm+1,tr,l,r,val);
ans[v]=max(ans[v*2],ans[v*2+1]);
}
int get(int v,int tl,int tr,int l,int r){
if(add[v])push(v,tl,tr);
if(r<tl or tr<l)return 0;
if(l<=tl && tr<=r)return ans[v];
int tm=(tl+tr)/2;
return max(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
int q;
cin>>q;
for(int i=0;i<q;i++){
int l,r;
cin>>l>>r;
qu[l].pb({r,i});
}
stack <int> st;
for(int i=n;i>=1;i--){
while(!st.empty() && a[st.top()]<=a[i]){
ab[i].pb(st.top());
st.pop();
}
if(!st.empty())ab[i].pb(st.top());
st.push(i);
}
vector <int> res(q);
for(int l=n;l>=1;l--){
for(auto b : ab[l]){
update(1,1,n,b*2-l,n,a[l]+a[b]);
}
for(auto x : qu[l]){
res[x.ss]=get(1,1,n,l,x.ff);
}
}
for(auto x : res)cout<<x<<"\n";
}
/*
*/
