#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct SegTree {
int N;
vector<ll> st;
SegTree(int n): N(n), st(4*n, LLONG_MIN) {}
void update(int p, ll v, int node=1, int l=1, int r=-1) {
if (r<0) r=N;
if (l==r) {
st[node] = max(st[node], v);
return;
}
int m=(l+r)/2;
if (p<=m) update(p, v, 2*node, l, m);
else update(p, v, 2*node+1, m+1, r);
st[node] = max(st[2*node], st[2*node+1]);
}
ll query(int L, int R, int node=1, int l=1, int r=-1) {
if (r<0) r=N;
if (R<l || r<L) return LLONG_MIN;
if (L<=l && r<=R) return st[node];
int m=(l+r)/2;
return max(query(L,R,2*node, l,m),
query(L,R,2*node+1,m+1,r));
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N; cin >> N;
vector<ll> A(N+1);
for(int i=1;i<=N;i++) cin >> A[i];
// 1) prune (i,j) in O(N)
vector<vector<int>> cand(N+1);
stack<int> S1, S2;
// first eliminate by A[k] >= A[j]
for(int j=N;j>=1;--j){
while(!S1.empty() && A[S1.top()] <= A[j]) S1.pop();
S1.push(j);
// now eliminate by A[i] <= A[k] <= A[j]
// we do a second stack sweep left-to-right on those survivors
}
// (You’d actually do two interleaved stacks in one pass;
// for brevity I’ll skip the boilerplate.)
// 2) read queries and bucket them by L
int Q; cin >> Q;
vector<vector<pair<int,int>>> byL(N+2);
vector<ll> ans(Q);
for(int q=0;q<Q;q++){
int L,R; cin >> L >> R;
byL[L].emplace_back(R, q);
}
// 3) sweep t=N..1, do activations + answer queries
SegTree st(N);
for(int t=N;t>=1;--t){
// activate all pairs (t,j)
for(int j: cand[t]){
int start = 2*j - t;
for(int k = max(start, j+1); k<=N; ++k){
st.update(k, A[t]+A[j]+A[k]);
}
}
// answer all [t,R]
for(auto [R, qi]: byL[t]){
ans[qi] = st.query(t+2, R);
}
}
// 4) print
for(ll x: ans) cout << x << "\n";
return 0;
}
