#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pi pair<int,int>
#define s second
#define f first
#define left (h<<1),l,((l+r)>>1)
#define right ((h<<1)|1),((l+r)>>1) + 1,r
using namespace std;
const int N = 500005;
int ans[N],t[4*N],add[4*N],T[4*N],n,a[N];
vector <pi> v[N];
vector <int> nx[N];
stack <int> st;
void go(){
for (int i = 1; i <= n; i++){
while (st.size() && a[i] >= a[st.top()]){
nx[st.top()].pb(i);
st.pop();
}
if (st.size())
nx[st.top()].pb(i);
st.push(i);
}
}
void build(int h,int l,int r){
if (l == r){
T[h] = a[l];
return;
}
build(left),build(right);
T[h] = max(T[h*2],T[h*2+1]);
}
void push(int h){
if (!add[h]) return;
t[h*2] = max(t[h*2],T[h*2] + add[h]);
t[h*2 + 1] = max(t[h*2 + 1],T[h*2 + 1] + add[h]);
add[h*2] = max(add[h*2],add[h]);
add[h*2 + 1] = max(add[h*2 + 1],add[h]);
add[h] = 0;
}
void upd(int h,int l,int r,int L,int R,int val){
if (r < L || R < l) return;
if (L <= l && r <= R){
t[h] = max(T[h] + val,t[h]);
add[h] = max(add[h],val);
return;
}
push(h);
upd(left,L,R,val),upd(right,L,R,val);
t[h] = max(t[h*2],t[h*2+1]);
}
int get(int h,int l,int r,int L,int R){
if (r < L || R < l) return 0;
if (L <= l && r <= R) return t[h];
push(h);
return max(get(left,L,R),get(right,L,R));
}
signed main (){
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
cin>>n;
for (int i = 1; i <= n; i++)
cin>>a[i];
go();
build(1,1,n);
int q;
cin>>q;
for (int i=1;i<=q;i++){
int l,r;
cin>>l>>r;
v[l].pb({r,i});
}
for (int i = n; i >= 1; i--){
for (auto id: nx[i]){
// a = i b = id c >= id + id - i
if (2*id - i <= n)
upd(1,1,n,2*id - i,n,a[i] + a[id]);
}
for (auto x: v[i])
ans[x.s] = get(1,1,n,i,x.f);
}
for (int i=1;i<=q;i++)
cout<<ans[i]<<"\n";
}
