#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Node {
ll best1, best2, best3;
// best1 = max A[i]
// best2 = max A[i]+A[j], i<j
// best3 = max A[x]+A[y]+A[z], x<y<z, with (y-x) <= (z-y)
};
vector<Node> seg;
int N, Q;
vector<ll> A;
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,
L.best1 + R.best2 });
return U;
}
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]);
}
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 L = query(idx<<1, l, m, ql, qr);
Node R = query(idx<<1|1, m+1, r, ql, qr);
return merge_node(L, R);
}
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.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);
// If there's no valid triple, best3 will be very negative.
// You can define what to print in that case; here we print best3 as is.
cout << ans.best3 << "\n";
}
return 0;
}
