#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static const ll NEGINF = (ll)-4e18;
struct Node {
// mx1 = maximum A[i] in the segment
// mx2 = maximum A[i] + A[j] for i<j in the segment
// mxAdj = maximum A[i] + A[i+1] for adjacent pair in the segment
// ans = maximum A[a]+A[b]+A[c] with a<b<c and (b−a) ≤ (c−b) in the segment
ll mx1, mx2, mxAdj, ans;
Node()
: mx1(NEGINF)
, mx2(NEGINF)
, mxAdj(NEGINF)
, ans(NEGINF)
{}
};
int N, Q;
vector<ll> A;
vector<Node> seg;
// Merge two child‐nodes L and R whose intervals are
// consecutive: [l..mid] and [mid+1..r]
Node mergeNode(const Node &L, const Node &R, int mid) {
Node res;
// best single
res.mx1 = max(L.mx1, R.mx1);
// best two‐sum (anywhere)
res.mx2 = max({ L.mx2,
R.mx2,
L.mx1 + R.mx1 });
// best adjacent‐pair sum
// either fully in L, fully in R, or straddling the boundary at mid/mid+1
res.mxAdj = max({ L.mxAdj,
R.mxAdj,
A[mid] + A[mid+1] });
// best triple:
// either entirely in L (L.ans)
// or entirely in R (R.ans)
// or two in L (an adjacent pair anywhere in L)
// plus best single in R
// or one in L (best single in L)
// plus two adjacent in R
ll cross1 = (L.mxAdj > NEGINF && R.mx1 > NEGINF
? L.mxAdj + R.mx1
: NEGINF);
ll cross2 = (L.mx1 > NEGINF && R.mxAdj > NEGINF
? L.mx1 + R.mxAdj
: NEGINF);
res.ans = max({ L.ans, R.ans, cross1, cross2 });
return res;
}
// build segment tree on [l..r] at index p
void build(int p, int l, int r) {
if (l == r) {
// leaf
seg[p].mx1 = A[l];
seg[p].mx2 = NEGINF;
seg[p].mxAdj = NEGINF;
seg[p].ans = NEGINF;
return;
}
int mid = (l + r) >> 1;
build(p<<1, l, mid);
build(p<<1|1, mid+1, r);
seg[p] = mergeNode(seg[p<<1], seg[p<<1|1], mid);
}
// query on [ql..qr], node at p covers [l..r]
Node query(int p, int l, int r, int ql, int qr) {
if (qr < l || r < ql) {
// completely outside
return Node();
}
if (ql <= l && r <= qr) {
// fully inside
return seg[p];
}
int mid = (l + r) >> 1;
Node left = query(p<<1, l, mid, ql, qr);
Node right = query(p<<1|1, mid+1, r, ql, qr);
// if one side is empty, return the other
if (left.mx1 == NEGINF) return right;
if (right.mx1 == NEGINF) return left;
// otherwise they are contiguous by construction
return mergeNode(left, right, mid);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
A.resize(N+1);
for(int i = 1; i <= N; i++){
cin >> A[i];
}
seg.assign(4*(N+1), Node());
build(1, 1, N);
cin >> Q;
while(Q--){
int L, R;
cin >> L >> R;
Node ans_node = query(1, 1, N, L, R);
// ans_node.ans holds the maximum A[a]+A[b]+A[c]
// under the constraint a<b<c, (b−a)≤(c−b)
// in the subarray [L..R].
cout << ans_node.ans << "\n";
}
return 0;
}
