///refers to Maripium's code
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 500100;
const ll inf = 1e18;
struct sta {
ll pref, ans, suf;
sta() : pref(-inf), ans(-inf), suf(-inf) {}
friend sta operator + (const sta &l, const sta &r) {
sta ans;
ans.pref = max(l.pref, r.pref);
ans.suf = max(l.suf, r.suf);
ans.ans = max({l.ans, r.ans, l.pref + r.suf});
return ans;
}
};
ll A[maxn], Ans[maxn];
sta T[maxn << 2];
vector<pair<int, ll>> es[maxn];
vector<pair<int, int>> qs[maxn];
void build(int v, int l, int r) {
if (l == r) {
T[v].suf = A[l];
return;
}
int md = (l + r) >> 1;
build(v << 1, l, md);
build(v << 1 | 1, md + 1, r);
T[v] = T[v << 1] + T[v << 1 | 1];
}
void upd(int v, int l, int r, int pos, ll val) {
if (l == r) {
T[v].pref = max(T[v].pref, val);
return;
}
int md = (l + r) >> 1;
if (pos <= md)
upd(v << 1, l, md, pos, val);
else
upd(v << 1 | 1, md + 1, r, pos, val);
T[v] = T[v << 1] + T[v << 1 | 1];
}
sta get(int v, int l, int r, int L, int R) {
if (L > r || R < l) return sta();
if (L <= l && r <= R) {
return T[v];
}
int md = (l + r) >> 1;
return get(v << 1, l, md, L, R) + get(v << 1 | 1, md + 1, r, L, R);
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int N; cin >> N;
stack<int> st;
for (int i = 1; i <= N; ++i) {
cin >> A[i];
while (!st.empty()) {
int id = 2 * i - st.top() - 1;
if (id < N) es[st.top()].emplace_back(A[i] + A[st.top()], id);
if (A[i] < A[st.top()]) break;
else st.pop();
}
st.push(i);
}
int Q; cin >> Q;
for (int l, r, i = 1; i <= Q; ++i) {
cin >> l >> r;
qs[l].emplace_back(r, i);
}
build(1, 1, N);
for (int i = N; i >= 1; --i) {
for (auto e : es[i]) {
upd(1, 1, N, e.second, e.first);
}
for (auto q : qs[i]) {
Ans[q.second] = get(1, 1, N, i, q.first).ans;
}
}
for (int i = 1; i <= Q; ++i) {
cout << Ans[i] << '\n';
}
return 0;
}
