#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 500055;
const int MAXQ = 500055;
struct NOD {
NOD(int a = 0, int b = 0, int c = 0)
: a(a), b(b), c(c) {}
int a, b, c;
NOD operator + (const NOD &t) const {
return NOD(max(a, t.a), max(b, t.b), max({c, t.c, b + t.a}));
}
};
struct SEG {
NOD nod[MAXN*3];
void init(int i, int s, int e, int A[]) {
if(s == e) {
nod[i].a = A[s];
nod[i].b = nod[i].c = -INF;
return;
}
int m = s+e >> 1;
init(i<<1, s, m, A);
init(i<<1|1, m+1, e, A);
nod[i] = nod[i<<1] + nod[i<<1|1];
}
void upd(int i, int s, int e, int x, int r) {
if(x < s || e < x) return;
if(s == e) {
upmax(nod[i].b, r);
nod[i].c = nod[i].a + nod[i].b;
return;
}
int m = s+e >> 1;
if(x <= m) upd(i<<1, s, m, x, r);
else upd(i<<1|1, m+1, e, x, r);
nod[i] = nod[i<<1] + nod[i<<1|1];
}
NOD get(int i, int s, int e, int p, int q) {
if(e < s || q < p || e < p || q < s) return NOD();
if(p <= s && e <= q) return nod[i];
int m = s+e >> 1;
return get(i<<1, s, m, p, q) + get(i<<1|1, m+1, e, p, q);
}
} seg;
vector<pii> TV[MAXN];
vector<int> QV[MAXN];
int A[MAXN];
int B[MAXQ], C[MAXQ];
int Ans[MAXQ];
int N, Q;
void precal() {
vector<pii> V = {{0, INF}};
for(int i = 1; i <= N; i++) {
for(int t; 1 < sz(V); V.pop_back()) {
t = i*2 - V.back().fi;
if(t <= N) TV[V.back().fi].eb(t, V.back().se + A[i]);
if(A[i] < V.back().se) break;
}
V.eb(i, A[i]);
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N;
for(int i = 1; i <= N; i++) cin >> A[i];
cin >> Q;
for(int i = 1; i <= Q; i++) {
cin >> B[i] >> C[i];
QV[B[i]].eb(i);
}
precal();
seg.init(1, 1, N, A);
for(int i = N; i; i--) {
for(auto &v : TV[i]) seg.upd(1, 1, N, v.fi, v.se);
for(int j : QV[i]) Ans[j] = seg.get(1, 1, N, B[j], C[j]).c;
}
for(int i = 1; i <= Q; i++)
cout << Ans[i] << '\n';
return 0;
}
