#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define mp make_pair
#define pb push_back
#define ld long double
#define ss(x) (int) x.size()
#define FOR(i, j, n) for(int i = j; i <= n; ++i)
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl;
#define ios cin.tie(0); ios_base::sync_with_stdio(0)
using namespace std;
const int nax = 6e5 + 111;
const int inf = 1e9 + 111;
const int pod = (1 << 19);
int n;
int a[nax];
int q, l, r;
int res[nax];
struct query {
int l, r, id;
};
vector <query> v;
vector <pair<int, int>> pairs;
stack <pair<int, int>> stos; // value, indeks
struct tree {
int lewo, prawo, best;
tree() {
lewo = -inf;
prawo = -inf;
best = -inf;
}
};
tree t[2 * pod];
void add(int u, int c) {
u += pod;
t[u].lewo = max(t[u].lewo, c);
t[u].best = max(t[u].best, t[u].lewo + t[u].prawo);
u /= 2;
while(u) {
t[u].lewo = max(t[2 * u].lewo, t[2 * u + 1].lewo);
t[u].best = max({t[2 * u].best, t[2 * u + 1].best, t[2 * u].lewo + t[2 * u + 1].prawo});
u /= 2;
}
}
tree merge(const tree &a, const tree &b) {
tree c = tree();
c.lewo = max(a.lewo, b.lewo);
c.prawo = max(a.prawo, b.prawo);
c.best = max({a.best, b.best, a.lewo + b.prawo});
return c;
}
tree Query(int x, int y, int u = 1, int l = 0, int r = pod - 1) {
if(x <= l && r <= y)
return t[u];
int m = (l + r) / 2;
tree ans = tree();
if(x <= m)
ans = merge(ans, Query(x, y, 2 * u, l, m));
if(m < y)
ans = merge(ans, Query(x, y, 2 * u + 1, m + 1, r));
return ans;
}
int main() {
scanf("%d", &n);
FOR(i, 1, n)
scanf("%d", &a[i]);
FOR(i, 1, n) {
while(!stos.empty() && stos.top().fi <= a[i]) {
pairs.pb(mp(stos.top().se, i));
stos.pop();
}
if(!stos.empty())
pairs.pb(mp(stos.top().se, i));
stos.push(mp(a[i], i));
}
sort(pairs.begin(), pairs.end());
scanf("%d", &q);
FOR(i, 1, q) {
scanf("%d %d", &l, &r);
query x = {l, r, i};
v.pb(x);
}
sort(v.begin(), v.end(), [](query a, query b) {
return a.l < b.l;
});
FOR(i, 0, pod - 1) {
t[i] = tree();
if(1 <= i && i <= n)
t[i + pod].prawo = a[i];
}
for(int i = pod - 1; 1 <= i; --i) {
t[i] = tree();
t[i].prawo = max(t[2 * i].prawo, t[2 * i + 1].prawo);
}
int wsk = ss(v) - 1;
int p = ss(pairs) - 1;
for(int i = n; 1 <= i; --i) {
while(p >= 0 && pairs[p].fi == i) {
int c = 2 * pairs[p].se - pairs[p].fi;
if(c <= n)
add(c, a[pairs[p].fi] + a[pairs[p].se]);
p -= 1;
}
while(wsk >= 0 && v[wsk].l == i) {
res[v[wsk].id] = Query(v[wsk].l, v[wsk].r).best;
wsk -= 1;
}
}
FOR(i, 1, q)
printf("%d\n", res[i]);
return 0;
}
