//雪花飄飄北風嘯嘯
//天地一片蒼茫
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n,q;
ll arr[500005];
vector<int> stk;
vector<ii> good;
struct Q{
int l,r;
int idx;
Q(int a,int b,int c){
l=a,r=b,idx=c;
}
};
vector<Q> queries;
int ans[500005];
struct dat{
ll ab=-1e18,c=0,abc=0;
};
dat merge(dat i,dat j){
dat res;
res.c=max(i.c,j.c);
res.ab=max(i.ab,j.ab);
res.abc=MAX(i.abc,j.abc,i.ab+j.c);
return res;
}
struct node{
int s,e,m;
dat val;
node *l,*r;
node (int _s,int _e){
s=_s,e=_e,m=s+e>>1;
if (s!=e){
l=new node(s,m);
r=new node(m+1,e);
val=merge(l->val,r->val);
}
else{
val.c=arr[s];
}
}
void update(int i,ll j){
if (s==e) val.ab=max(val.ab,j);
else{
if (i<=m) l->update(i,j);
else r->update(i,j);
val=merge(l->val,r->val);
}
}
dat query(int i,int j){
if (s==i && e==j) return val;
else if (j<=m) return l->query(i,j);
else if (m<i) return r->query(i,j);
else return merge(l->query(i,m),r->query(m+1,j));
}
} *root;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
rep(x,0,n) cin>>arr[x];
root=new node(0,500005);
rep(x,0,n){
while (!stk.empty() && arr[stk.back()]<=arr[x]){
good.push_back({stk.back(),x});
stk.pop_back();
}
if (!stk.empty()) good.push_back({stk.back(),x});
stk.push_back(x);
}
cin>>q;
int a,b;
rep(x,0,q){
cin>>a>>b;
a--,b--;
queries.push_back(Q(a,b,x));
}
sort(all(good),[](ii i,ii j){
return i.fi<j.fi;
});
sort(all(queries),[](Q &i,Q &j){
return i.l>j.l;
});
for (auto &it:queries){
while (!good.empty() && it.l<=good.back().fi){
int pos=good.back().se*2-good.back().fi-1;
//cout<<pos<<" "<<good.back().fi<<" "<<good.back().se<<endl;
if (pos<200005) root->update(pos,arr[good.back().fi]+arr[good.back().se]);
good.pop_back();
}
ans[it.idx]=root->query(0,it.r).abc;
}
rep(x,0,q) cout<<ans[x]<<endl;
}
