#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e14;
const int N = 5e5 + 5;
struct node {
ll A, B, BA;
node(ll _A = -INF, ll _B = -INF, ll _BA = -INF) {
A = _A, B = _B, BA = _BA;
}
};
node tree[4 * N];
int n, q;
ll a[N];
vector <int> r[N];
vector <pair <int, int>> Q[N];
node merge(node x, node y) {
return node(max(x.A, y.A), max(x.B, y.B), max({x.BA, y.BA, x.B + y.A}));
}
void update(int node, int s, int e, int idx, ll val, bool flag) {
if(idx < s or idx > e) return;
if(s == e) {
if(flag) tree[node].B = max(tree[node].B, val);
else tree[node].A = max(tree[node].A, val);
tree[node].BA = max(-INF, tree[node].A + tree[node].B);
return;
}
int mid = (s + e) / 2;
update(2 * node, s, mid, idx, val, flag);
update(2 * node + 1, mid + 1, e, idx, val, flag);
tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
}
node query(int node, int s, int e, int l, int r) {
if(l > e or r < s) return {-INF, -INF, -INF};
if(s >= l and e <= r) {
return tree[node];
}
int mid = (s + e) / 2;
return merge(query(2 * node, s, mid, l, r), query(2 * node + 1, mid + 1, e, l, r));
}
int main() {
scanf("%d", &n);
stack <ll> s;
for(int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
while(!s.empty() and a[s.top()] <= a[i]) {
r[s.top()].push_back(i);
s.pop();
}
if(!s.empty()) {
r[s.top()].push_back(i);
}
s.push(i);
update(1, 1, n, i, a[i], 0);
}
scanf("%d", &q);
for(int i = 0; i < q; i++) {
int l, r; scanf("%d %d", &l, &r);
Q[l].push_back({r, i});
}
vector <ll> ans(q);
for(int i = n; i >= 1; i--) {
for(auto p : r[i]) {
if(p + p - i <= n) {
update(1, 1, n, p + p - i, a[p] + a[i], 1);
}
}
for(auto p : Q[i]) {
ans[p.second] = query(1, 1, n, i, p.first).BA;
}
}
for(int i = 0; i < q; i++) {
printf("%lld\n", ans[i]);
}
}
