#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 5e5+5;
int n,q,a[N],lazy[4*N],st1[4*N],st2[4*N],ans[N];
stack<int>st;
vector<pii>adj[N];
void build(int id, int l, int r){
if(l == r){
st1[id] = a[l];
return;
}
int mid = (l+r)/2;
build(2*id,l,mid);
build(2*id+1,mid+1,r);
st1[id] = max(st1[2*id],st1[2*id+1]);
}
void down(int id){
if(lazy[id] != 0){
st2[2*id] = max(st2[2*id],lazy[id]+st1[2*id]);
st2[2*id+1] = max(st2[2*id+1],lazy[id]+st1[2*id+1]);
lazy[2*id] = max(lazy[2*id],lazy[id]);
lazy[2*id+1] = max(lazy[2*id+1],lazy[id]);
lazy[id] = 0;
}
}
void update(int id, int l, int r, int u, int v, int val){
if(l > v || r < u) return;
if(l >= u && r <= v){
st2[id] = max(st2[id],val+st1[id]);
lazy[id] = max(lazy[id],val);
return;
}
if(l != r) down(id);
int mid = (l+r)/2;
update(2*id,l,mid,u,v,val);
update(2*id+1,mid+1,r,u,v,val);
st2[id] = max(st2[2*id],st2[2*id+1]);
}
int get(int id, int l, int r, int u, int v){
if(l != r) down(id);
if(l > v || r < u) return 0;
if(l >= u && r <= v) return st2[id];
int mid = (l+r)/2;
return max(get(2*id,l,mid,u,v),get(2*id+1,mid+1,r,u,v));
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
build(1,1,n);
cin >> q;
for(int i = 1; i <= q; i++){
int l,r;
cin >> l >> r;
adj[l].push_back({r,i});
}
for(int i = n; i >= 1; i--){
while(!st.empty() && a[st.top()] < a[i]){
int x = 2*st.top()-i;
update(1,1,n,x,n,a[i]+a[st.top()]);
st.pop();
}
if(!st.empty()){
int x = 2*st.top()-i;
update(1,1,n,x,n,a[i]+a[st.top()]);
}
st.push(i);
for(auto[v,id]: adj[i]) ans[id] = get(1,1,n,i,v);
}
for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}
