#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int N = 5e5 + 10;
const ll inf = 1e18;
int n, q, a[N], ans[N];
vector<ii> Q[N];
vector<int> B[N];
struct Node {
ll a, f, af;
Node(ll a = -inf, ll f = -inf, ll af = -inf):
a(a), f(f), af(af) {}
} t[N << 2];
Node merge(Node l, Node r) {
return Node(max(l.a, r.a), max(l.f, r.f), max({l.af, r.af, l.f + r.a}));
}
void update(int node, int l, int r, int i, int x, int f) {
if(l == r) {
if(f) t[node].f = max(t[node].f, (ll)x);
else t[node].a = max(t[node].a, (ll)x);
t[node].af = max(-inf, t[node].f + t[node].a);
} else {
int m = l + r >> 1;
if(i <= m) update(node << 1, l, m, i, x, f);
else update(node << 1 | 1, m + 1, r, i, x, f);
t[node] = merge(t[node << 1], t[node << 1 | 1]);
}
}
Node query(int node, int l, int r, int i, int j) {
if(r < i || l > j) return Node();
if(i <= l && r <= j) return t[node];
int m = l + r >> 1;
return merge(query(node << 1, l, m, i, j),
query(node << 1 | 1, m + 1, r, i, j));
}
int main(int argc, char const *argv[]) {
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
scanf("%d", &n);
stack<int> st;
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
while(st.size() && a[st.top()] <= a[i]) {
B[st.top()].push_back(i);
st.pop();
}
if(st.size()) {
B[st.top()].push_back(i);
}
st.push(i);
update(1, 1, n, i, a[i], 0);
}
scanf("%d", &q);
for(int i = 1; i <= q; ++i) {
int l, r;
scanf("%d %d", &l, &r);
Q[l].emplace_back(r, i);
}
for(int i = n; i >= 1; --i) {
for(int b : B[i]) if(2 * b - i <= n) {
update(1, 1, n, 2 * b - i, a[i] + a[b], 1);
}
for(ii x : Q[i]) {
ans[x.second] = query(1, 1, n, i, x.first).af;
}
}
for(int i = 1; i <= q; ++i) {
printf("%lld\n", ans[i]);
}
}
