#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
const int N = 5e5 + 5;
int n, q, a[N], l[N], r[N];
stack<int> st;
using pii = pair<int, int>;
#define fi first
#define se second
vector<pii> query_l[N];
vector<int> being_i[N];
ll tot[4*N], seg[4*N], lazy[4*N], res[N];
void build(int root, int tl, int tr) {
lazy[root] = -INF;
if (tl == tr) {
seg[root] = a[tl];
tot[root] = seg[root] + lazy[root];
return;
}
int tm = (tl + tr) / 2;
build(2*root, tl, tm);
build(2*root+1, tm+1, tr);
seg[root] = max(seg[2*root], seg[2*root+1]);
tot[root] = max(tot[2*root], tot[2*root+1]);
}
void cmax(ll &x, ll y) {x = max(x, y);}
void upd(int root, ll v) {
cmax(lazy[root], v);
cmax(tot[root], seg[root] + lazy[root]);
}
void update(int root, int tl, int tr, int l, int r, ll v) {
if (tl > r || tr < l) return;
if (tl >= l && tr <= r) {
upd(root, v);
return;
}
int tm = (tl + tr) / 2;
upd(2*root, lazy[root]);
upd(2*root+1, lazy[root]);
update(2*root, tl, tm, l, r, v);
update(2*root+1, tm+1, tr, l, r, v);
tot[root] = max(tot[2*root], tot[2*root+1]);
}
ll get(int root, int tl, int tr, int l, int r) {
if (tl > r || tr < l) return 0LL;
if (tl >= l && tr <= r) return tot[root];
int tm = (tl + tr) / 2;
upd(2*root, lazy[root]);
upd(2*root+1, lazy[root]);
return max(get(2*root, tl, tm, l, r),
get(2*root+1, tm+1, tr, l, r));
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen("triple.inp", "r", stdin);
//freopen("triple.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
l[i] = 0, r[i] = n+1;
for (int i = 1; i <= n; i++) {
while (!st.empty() && a[st.top()] < a[i]) st.pop();
if (!st.empty()) l[i] = st.top();
st.push(i);
}
while (!st.empty()) st.pop();
for (int i = n; i >= 1; i--) {
while (!st.empty() && a[st.top()] < a[i]) st.pop();
if (!st.empty()) r[i] = st.top();
st.push(i);
}
for (int i = 1; i <= n; i++) {
if (l[i] > 0) being_i[l[i]].push_back(i);
if (r[i] < n+1) being_i[i].push_back(r[i]);
}
cin >> q;
for (int i = 1; i <= q; i++) {
int x, y;
cin >> x >> y;
query_l[x].emplace_back(y, i);
}
build(1, 1, n);
for (int i = n; i >= 1; i--) {
for (auto c: being_i[i]) {
update(1, 1, n, 2*c - i, n, a[c] + a[i]);
}
for (auto c: query_l[i]) {
res[c.se] = get(1, 1, n, i, c.fi);
}
}
for (int i = 1; i <= q; i++) cout << res[i] << '\n';
}
