#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 500500;
const ll inf = 1e18;
struct State {
ll pref, suf, ans;
State() : pref(-inf), suf(-inf), ans(-inf) {}
friend State operator + (const State &l, const State &r) {
State 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[N];
State t[N << 2];
ll ans[N];
vector<pair<int, ll>> es[N];
vector<pair<int, int>> qs[N];
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 mdf(int v, int l, int r, int p, ll val) {
if (l == r) {
t[v].pref = max(t[v].pref, val);
return;
}
int md = (l + r) >> 1;
if (p <= md) {
mdf(v << 1, l, md, p, val);
} else {
mdf(v << 1 | 1, md + 1, r, p, val);
}
t[v] = t[v << 1] + t[v << 1 | 1];
}
State get(int v, int l, int r, int L, int R) {
if (L > r || R < l) return State();
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_base::sync_with_stdio(false);
int n;
cin >> n;
vector<int> st;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
while (!st.empty()) {
int go = 2 * i - st.back() - 1;
if (go < n) es[st.back()].emplace_back(a[i] + a[st.back()], go);
if (a[i] < a[st.back()]) {
break;
} else {
st.pop_back();
}
}
st.emplace_back(i);
}
int q;
cin >> q;
for (int i = 1; i <= q; ++i) {
int l, r;
cin >> l >> r;
qs[l].emplace_back(r, i);
}
build(1, 1, n);
for (int i = n; i > 0; --i) {
for (auto e : es[i]) {
mdf(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";
}
}
