#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 500005, Q = 500005;
int n, q, l, r, a[N], ans[Q];
vector<int> pos;
vector<pair<int, int>> upd[N], que[N];
struct STree
{
#define m (l + r) / 2
#define lc i * 2
#define rc i * 2 + 1
int tot[4 * N], cur[4 * N] , lz[4 * N];
void apply(int i, int v)
{
lz[i] = max(lz[i], v);
tot[i] = max(tot[i], cur[i] + lz[i]);
}
void down(int i)
{
apply(lc, lz[i]);
apply(rc, lz[i]);
lz[i] = 0;
}
void update_range(int l, int r, int i, int L, int R, int v)
{
if (l > R || r < L || L > R)
return;
if (L <= l && r <= R)
{
apply(i, v);
return;
}
down(i);
update_range(l, m, lc, L, R, v);
update_range(m + 1, r, rc, L, R, v);
tot[i] = max(tot[lc], tot[rc]);
}
void update_node(int l, int r, int i, int u, int v)
{
if (l > u || r < u)
return;
if (l == r)
{
cur[i] = v; lz[i] = 0;
apply(i, 0);
return;
}
down(i);
if (u <= m)
update_node(l, m, lc, u, v);
else
update_node(m + 1, r, rc, u, v);
cur[i] = max(cur[lc], cur[rc]);
tot[i] = max(tot[lc], tot[rc]);
}
int query(int l, int r, int i, int L, int R)
{
if (l > R || r < L || L > R)
return 0;
else if (L <= l && r <= R)
return tot[i];
down(i);
return max(query(l, m, lc, L, R), query(m + 1, r, rc, L, R));
}
#undef m
#undef lc
#undef rc
} seg;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
while (!pos.empty())
{
int u = pos.back();
if (2 * i - u <= n)
upd[2 * i - u].push_back({u, a[i] + a[u]});
if (a[u] <= a[i])
pos.pop_back();
else
break;
}
pos.push_back(i);
}
cin >> q;
for (int i = 1; i <= q; i++)
{
cin >> l >> r;
que[r].push_back({l, i});
}
for (int i = 1; i <= n; i++)
{
for (pair<int, int> &v : upd[i])
seg.update_node(1, n, 1, v.fi, v.se);
seg.update_range(1, n, 1, 1, i, a[i]);
for (pair<int, int> &v : que[i])
ans[v.se] = seg.query(1, n, 1, v.fi, i);
}
for (int i = 1; i <= q; i++)
cout << ans[i] << '\n';
}
