#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Node {
ll best; // best triple A[a]+A[b]+A[c]
ll mx; // max A[x]
vector<ll> L; // L[d] = best A[a]+A[a+d] in left half
vector<ll> R; // R[d] = best A[c-d]+A[c] in right half
Node(): best(0), mx(0) {}
};
int N;
vector<ll> A;
vector<Node> seg;
// Merge two nodes a=[l..m], b=[m+1..r] into res=[l..r]
Node merge(const Node &a, const Node &b) {
int nl = (int)a.L.size() + (int)a.R.size() + 1; // not actually used
Node res;
res.mx = max(a.mx, b.mx);
// 1) best entirely in one side
res.best = max(a.best, b.best);
// Prepare L for res: pairs entirely in left child or crossing
int lenL = a.L.size() + 1; // interval length of left child
int lenR = b.R.size() + 1; // length of right child
int len = lenL + lenR;
res.L.assign(len, LLONG_MIN);
res.R.assign(len, LLONG_MIN);
// 2) copy old L pairs from a
for (int d = 1; d < (int)a.L.size(); d++)
res.L[d] = max(res.L[d], a.L[d]);
// 3) pairs entirely in b but re‐indexed to global
for (int d = 1; d < (int)b.L.size(); d++)
res.L[d + lenL] = max(res.L[d + lenL], b.L[d]);
// 4) similarly for R
for (int d = 1; d < (int)b.R.size(); d++)
res.R[d] = max(res.R[d], b.R[d]);
for (int d = 1; d < (int)a.R.size(); d++)
res.R[d + lenR] = max(res.R[d + lenR], a.R[d]);
// 5) now handle triples that cross—i.e. a pair from left child of offset d1,
// a single from the boundary, and a pair from right child of offset d2,
// subject to d1 <= d2.
// Actually it suffices to scan all d where both res.L[d], res.R[d] are valid:
for (int d = 1; d < len; d++) {
if (res.L[d] > LLONG_MIN/2 && res.R[d] > LLONG_MIN/2) {
res.best = max(res.best, res.L[d] + res.R[d] - /*A[b] counted twice*/ 0);
}
}
// Finally, any triple using two from one side and one singleton from the other?
// Actually those are already included in a.best or b.best, or in the scan above.
return res;
}
void build(int idx, int l, int r) {
if (l == r) {
seg[idx].best = 0; // no triple in a single point
seg[idx].mx = A[l];
seg[idx].L = seg[idx].R = vector<ll>(2, LLONG_MIN);
// no valid d=1 pair in a single point
return;
}
int m = (l + r) >> 1;
build(idx<<1, l, m);
build(idx<<1|1, m+1, r);
seg[idx] = merge(seg[idx<<1], seg[idx<<1|1]);
}
Node query(int idx, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return seg[idx];
int m = (l + r) >> 1;
if (qr <= m) return query(idx<<1, l, m, ql, qr);
if (ql > m) return query(idx<<1|1, m+1, r, ql, qr);
return merge(
query(idx<<1, l, m, ql, qr),
query(idx<<1|1, m+1, r, ql, qr)
);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int Q;
cin >> N;
A.resize(N+1);
for (int i = 1; i <= N; i++) cin >> A[i];
seg.resize(4*(N+1));
build(1, 1, N);
cin >> Q;
while (Q--) {
int L, R;
cin >> L >> R;
auto ans = query(1, 1, N, L, R);
cout << ans.best << "\n";
}
return 0;
}
