#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std;
typedef pair<int, int> pii;
int n, q;
int A[500001];
pair<pii, int> Q[500000];
int ans[500000];
int L[500002];
int R[500002];
vector<int> P[500001];
const int inf = 1e9;
struct node {
int L, R, LR;
node() : L(-inf), R(-inf), LR(-inf) {}
node operator+(const node &p) const {
node ret = node();
ret.L = max(L, p.L);
ret.R = max(R, p.R);
ret.LR = max({ LR, p.LR, L + p.R });
return ret;
}
} seg[1 << 20];
void init(int i, int s, int e) {
if (s == e) {
seg[i].R = A[s];
seg[i].LR = seg[i].L + seg[i].R;
return;
}
int m = (s + e) / 2;
init(i << 1, s, m);
init(i << 1 | 1, m + 1, e);
seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
void update(int i, int s, int e, int x, int v) {
if (s == e) {
seg[i].L = max(seg[i].L, v);
seg[i].LR = seg[i].L + seg[i].R;
return;
}
int m = (s + e) / 2;
if (x <= m) update(i << 1, s, m, x, v);
else update(i << 1 | 1, m + 1, e, x, v);
seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
node query(int i, int s, int e, int x) {
if (x < s) return node();
if (e <= x) return seg[i];
int m = (s + e) / 2;
return query(i << 1, s, m, x) + query(i << 1 | 1, m + 1, e, x);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n;
vector<pii> B;
for (int i = 1; i <= n; ++i) {
cin >> A[i];
B.emplace_back(A[i], i);
}
cin >> q;
for (int i = 0; i < q; ++i) {
cin >> Q[i].first.first >> Q[i].first.second;
Q[i].second = i;
}
sort(Q, Q + q);
sort(B.begin(), B.end());
for (pii it : B) {
int i = it.second;
int l = i, r = i;
if (L[i - 1] != 0) l = L[i - 1];
if (R[i + 1] != 0) r = R[i + 1];
L[l] = L[r] = l;
R[l] = R[r] = r;
if (l > 1) P[l - 1].push_back(i);
if (r < n) P[i].push_back(r + 1);
}
init(1, 1, n);
for (int i = q, j = n + 1; i--; ) {
int l, r;
tie(l, r) = Q[i].first;
while (j > l) {
for (int k : P[--j]) {
int x = k + k - j;
if (x > n) continue;
int v = A[j] + A[k];
update(1, 1, n, x, v);
}
}
ans[Q[i].second] = query(1, 1, n, r).LR;
}
for (int i = 0; i < q; ++i) printf("%d\n", ans[i]);
return 0;
}
