#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second
#define hash vector<int>
#define REP(i, n) for (int i = 1, _n = (n); i <= _n; i++)
#define REV(i, n) for (int i = (n); i >= 1; i--)
#define FOR(i, k, n) for (int i = (k), _n = (n); i <= _n; i++)
#define FOV(i, k, n) for (int i = (n), _n = (k); i >= _n; i--)
#define MASK(k) (1 << (k))
#define BIT(i, n) (((n) >> ((i) - 1)) & 1)
#define OFF(i, n) ((n) & ~MASK((i) - 1))
#define ON(i, n) ((n) | MASK((i) - 1))
#define NUM_BIT(n) (__builtin_popcount(n))
const int MAXN = 1e6 + 26;
int n, m, k, x, y, a[MAXN], ans[MAXN];
pii c[MAXN];
ll lazy[4 * MAXN];
struct Node {
ll mx, pr;
Node(ll val = 0) {
mx = pr = val;
}
} tree[4 * MAXN];
void build(int k, int l, int r) {
if (l == r) return tree[k] = Node(a[r]), void();
int m = (l + r) >> 1;
build(k << 1, l, m);
build(k << 1 | 1, m + 1, r);
tree[k].mx = max(tree[k << 1].mx, tree[k << 1 | 1].mx);
tree[k].pr = max(tree[k << 1].pr, tree[k << 1 | 1].pr);
}
void fix(int k, int l, int r) {
if (!lazy[k]) return;
tree[k].mx = max(tree[k].mx, tree[k].pr + lazy[k]);
if (l != r) {
lazy[k << 1] = max(lazy[k << 1], lazy[k]);
lazy[k << 1 | 1] = max(lazy[k << 1 | 1], lazy[k]);
}
lazy[k] = 0;
}
void update(int k, int l, int r, int u, int v, ll f) {
fix(k, l, r);
if (l > v || r < u) return;
if (l >= u && r <= v) {
lazy[k] = max(lazy[k], f);
fix(k, l, r);
return;
}
int m = (l + r) >> 1;
update(k << 1, l, m, u, v, f);
update(k << 1 | 1, m + 1, r, u, v, f);
tree[k].mx = max(tree[k << 1].mx, tree[k << 1 | 1].mx);
}
ll get(int k, int l, int r, int u, int v) {
fix(k, l, r);
if (l > v || r < u) return -1e18;
if (l >= u && r <= v) return tree[k].mx;
int m = (l + r) >> 1;
return max(get(k << 1, l, m, u, v), get(k << 1 | 1, m + 1, r, u, v));
}
struct query {
int l, r, id;
} b[MAXN];
void find_pairs() {
stack<int> st;
REP(i, n) {
while (!st.empty() && a[st.top()] <= a[i]) {
c[++k] = {st.top(), i};
st.pop();
}
if (!st.empty()) c[++k] = {st.top(), i};;
st.push(i);
}
sort(c + 1, c + k + 1, greater<pii>());
}
bool cmp(query i1, query i2) {
return i1.l < i2.l;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
REP(i, n) cin >> a[i];
cin >> m;
REP(i, m) cin >> x >> y, b[i] = {x, y, i};
find_pairs();
build(1, 1, n);
sort(b + 1, b + m + 1, cmp);
int j = 1;
REP(i, m) {
int l = b[i].l, r = b[i].r;
while (c[j].fi >= l && j <= k) {
int x = c[j].fi, y = c[j].se;
int p = 2 * y - x;
if (p <= n) update(1, 1, n, p, n, a[x] + a[y]);
j++;
}
int id = b[i].id;
ans[id] = get(1, 1, n, l, r);
}
REP(i, m) cout << ans[i] << endl;
return 0;
}
