#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int MAXN = 5.1e5;
int N;
int A[MAXN];
struct node_t {
int base;
int add;
int best;
node_t() {}
node_t(int base_, int add_, int best_) : base(base_), add(add_), best(best_) {}
node_t operator + (const node_t& o) const {
node_t res;
res.base = max(base, o.base);
res.add = max(add, o.add);
res.best = max({best, o.best, add + o.base});
return res;
}
};
struct seg {
seg* ch[2];
node_t res;
seg() {}
void update() {
assert(ch[0]);
res = ch[0]->res + ch[1]->res;
}
};
seg nodes[MAXN*2];
int NODE;
seg* ROOT;
seg* build(int x = 0, int y = N) {
seg* r = &nodes[NODE++];
if (y - x == 1) {
r->res = node_t(A[x], -INF, -INF);
} else {
int z = (x + y) / 2;
r->ch[0] = build(x, z);
r->ch[1] = build(z, y);
r->update();
}
return r;
}
void update(int k, int v, int x = 0, int y = N, seg* n = ROOT) {
if (y - x == 1) {
n->res.add = max(n->res.add, v);
n->res.best = n->res.base + n->res.add;
} else {
int z = (x + y) / 2;
if (k < z) {
update(k, v, x, z, n->ch[0]);
} else {
update(k, v, z, y, n->ch[1]);
}
n->update();
}
}
node_t query(int l, int r, int x = 0, int y = N, seg* n = ROOT) {
if (l <= x && y <= r) {
return n->res;
} else {
int z = (x + y) / 2;
if (r <= z) {
return query(l, r, x, z, n->ch[0]);
} else if (z <= l) {
return query(l, r, z, y, n->ch[1]);
} else {
return query(l, r, x, z, n->ch[0]) + query(l, r, z, y, n->ch[1]);
}
}
}
vector<int> candidates[MAXN];
vector<array<int, 2>> queries[MAXN];
const int MAXQ = 5.1e5;
int ans[MAXQ];
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> A[i];
}
vector<int> st;
for (int i = 0; i < N; i++) {
while (!st.empty() && A[st.back()] <= A[i]) {
candidates[st.back()].push_back(i);
st.pop_back();
}
if (!st.empty()) {
candidates[st.back()].push_back(i);
}
st.push_back(i);
}
int Q; cin >> Q;
for (int q = 0; q < Q; q++) {
int l, r; cin >> l >> r; l--;
queries[l].push_back({r, q});
}
ROOT = build();
for (int l = N-1; l >= 0; l--) {
for (int r : candidates[l]) {
int x = 2 * r - l;
if (x < N) {
update(x, A[l] + A[r]);
}
}
for (auto q : queries[l]) {
ans[q[1]] = query(l, q[0]).best;
}
}
for (int q = 0; q < Q; q++) {
cout << ans[q] << '\n';
}
return 0;
}
