#include <bits/stdc++.h>
using namespace std;
const int nmax = 500005;
vector< pair<int, int> > l[nmax], qr[nmax];
int v[nmax], st[nmax], an[nmax];
int n, i, j, u, q, L, R;
struct node {
int L, R, LR;
} arb[4 * nmax], ans;
void add(int x, int y) {
if(2 * y - x <= n)
l[x].push_back({2 * y - x, v[x] + v[y]});
}
void mrg(node &A, node B, node C) {
A.L = max(B.L, C.L);
A.R = max(B.R, C.R);
A.LR = max(B.LR, C.LR);
A.LR = max(A.LR, B.L + C.R);
}
void update(int nod, int l, int r, int poz, int val, int tip) {
if(l == r) {
if(tip) arb[nod].R = max(arb[nod].R, val);
else arb[nod].L = max(arb[nod].L, val);
arb[nod].LR = arb[nod].L + arb[nod].R;
return;
}
int m = (l + r) / 2;
if(poz <= m) update(2 * nod, l, m, poz, val, tip);
else update(2 * nod + 1, m + 1, r, poz, val, tip);
mrg(arb[nod], arb[2 * nod], arb[2 * nod + 1]);
}
void query(int nod, int l, int r, int st, int dr) {
if(st <= l && r <= dr) {
mrg(ans, ans, arb[nod]);
return;
}
int m = (l + r) / 2;
if(st <= m) query(2 * nod, l, m, st, dr);
if(m < dr) query(2 * nod + 1, m + 1, r, st, dr);
}
int Q(int S, int D) {
ans = {-(1 << 29), -(1 << 29), -(1 << 29)};
query(1, 1, n, S, D);
return ans.LR;
}
int main() {
ios_base::sync_with_stdio(false);
cin >> n;
for(i = 1; i <= n; i++) {
cin >> v[i];
while(u > 0 && v[i] > v[st[u]]) {
add(st[u], i);
u--;
}
if(u) add(st[u], i);
st[++u] = i;
}
cin >> q;
for(i = 1; i <= q; i++) {
cin >> L >> R;
qr[L].push_back({R, i});
}
for(i = 1; i <= 4 * n; i++) {
arb[i].L = arb[i].R = arb[i].LR = -(1 << 29);
}
for(i = n; i >= 1; i--) {
update(1, 1, n, i, v[i], 1);
for(auto it : l[i])
update(1, 1, n, it.first, it.second, 0);
for(auto it : qr[i])
an[it.second] = Q(i, it.first);
}
for(i = 1; i <= q; i++)
cout << an[i] << '\n';
return 0;
}
