#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Node {
ll best1; // max A[i]
ll best2; // max A[i]+A[j] for i<j
ll best3; // max A[x]+A[y]+A[z] with x<y<z and (y-x)<= (z-y)
};
int N, Q;
vector<ll> A;
vector<Node> seg;
// Merge two adjacent segments L and R into U
Node merge_node(const Node &L, const Node &R) {
Node U;
U.best1 = max(L.best1, R.best1);
U.best2 = max({ L.best2,
R.best2,
L.best1 + R.best1 });
U.best3 = max({ L.best3,
R.best3,
L.best2 + R.best1, // x,y in L; z in R
L.best1 + R.best2 // x in L; y,z in R
});
return U;
}
// Build segment tree over [l..r]
void build(int idx, int l, int r) {
if (l == r) {
seg[idx] = { A[l], LLONG_MIN/2, LLONG_MIN/2 };
return;
}
int m = (l + r) >> 1;
build(idx<<1, l, m);
build(idx<<1|1, m+1, r);
seg[idx] = merge_node(seg[idx<<1], seg[idx<<1|1]);
}
// Query segment tree on [ql..qr]
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);
Node left = query(idx<<1, l, m, ql, qr);
Node right= query(idx<<1|1, m+1, r, ql, qr);
return merge_node(left, right);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Input
cin >> N;
A.resize(N+1);
for (int i = 1; i <= N; i++) {
cin >> A[i];
}
cin >> Q;
// Build tree
seg.resize(4*(N+1));
build(1, 1, N);
// Process queries
while (Q--) {
int l, r;
cin >> l >> r;
Node res = query(1, 1, N, l, r);
// If no valid triple exists, res.best3 will be very negative.
cout << res.best3 << "\n";
}
return 0;
}
