#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;
#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
constexpr int mxN = 500005;
int N, Q, A[mxN];
vt<ari2> queries[mxN];
vt<int> bs[mxN];
struct ST {
struct Node {
int ans, c, ab;
Node operator+(const Node &other) {
return {
max({ans, other.ans, ab + other.c}),
max(c, other.c),
max(ab, other.ab)
};
}
} st[mxN<<1];
void build() {
FOR(i, 0, N-1)
st[i+N] = {0, A[i], 0};
ROF(i, N-1, 1)
st[i] = st[i<<1] + st[i<<1|1];
}
void update(int i, int v) {
i += N;
st[i].ab = max(st[i].ab, v);
st[i].ans = st[i].ab + st[i].c;
for (i >>= 1; i > 0; i >>= 1)
st[i] = st[i<<1] + st[i<<1|1];
}
Node query(int l, int r) {
Node lft = {0, 0, 0}, rht = {0, 0, 0};
for (l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
if (l & 1)
lft = lft + st[l++];
if (r & 1)
rht = st[--r] + rht;
}
return lft + rht;
}
} st;
signed main() {
#ifndef DEBUG
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#endif
cin >> N;
FOR(i, 0, N-1)
cin >> A[i];
cin >> Q;
FOR(i, 0, Q-1) {
int l, r; cin >> l >> r, l--, r--;
queries[l].push_back({r, i});
}
vt<int> sk;
FOR(i, 0, N-1) {
while (size(sk) && A[sk.back()] <= A[i]) {
bs[sk.back()].push_back(i);
sk.pop_back();
}
if (size(sk))
bs[sk.back()].push_back(i);
sk.push_back(i);
}
st.build();
vt<int> ans(Q);
ROF(i, N-3, 0) {
for (int j : bs[i]) {
if (2 * j - i >= N)
continue;
st.update(2 * j - i, A[i] + A[j]);
}
for (auto [r, qi] : queries[i])
ans[qi] = st.query(i, r).ans;
}
for (auto &i : ans)
cout << i << '\n';
}
