#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 5e5 + 5;
int n, q, arr[MAXN];
ll answer[MAXN];
vector<pair<int, int>> queries[MAXN];
class SegmentTree
{
vector<ll> tree, lazy, maxval;
int size;
public:
SegmentTree(int n, int *a)
{
size = n;
tree.resize(n << 2);
lazy.resize(n << 2);
maxval.resize(n << 2);
build(1, n, 1, a);
}
void build(int l, int r, int idx, int *a)
{
if (l == r)
{
maxval[idx] = a[l];
return;
}
int m = (l + r) >> 1;
build(l, m, idx << 1, a);
build(m + 1, r, idx << 1 | 1, a);
maxval[idx] = max(maxval[idx << 1], maxval[idx << 1 | 1]);
}
void push(int idx)
{
if (!lazy[idx])
return;
for (int d = 0; d < 2; ++d)
{
int child = idx << 1 | d;
tree[child] = max(tree[child], lazy[idx] + maxval[child]);
lazy[child] = max(lazy[child], lazy[idx]);
}
lazy[idx] = 0;
}
void update(int l, int r, ll val, int tl = 1, int tr = -1, int idx = 1)
{
if (tr == -1)
tr = size;
if (r < tl || tr < l)
return;
if (l <= tl && tr <= r)
{
tree[idx] = max(tree[idx], val + maxval[idx]);
lazy[idx] = max(lazy[idx], val);
return;
}
push(idx);
int m = (tl + tr) >> 1;
update(l, r, val, tl, m, idx << 1);
update(l, r, val, m + 1, tr, idx << 1 | 1);
tree[idx] = max(tree[idx << 1], tree[idx << 1 | 1]);
}
ll query(int l, int r, int tl = 1, int tr = -1, int idx = 1)
{
if (tr == -1)
tr = size;
if (r < tl || tr < l)
return 0;
if (l <= tl && tr <= r)
return tree[idx];
push(idx);
int m = (tl + tr) >> 1;
return max(query(l, r, tl, m, idx << 1),
query(l, r, m + 1, tr, idx << 1 | 1));
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &arr[i]);
scanf("%d", &q);
for (int i = 1; i <= q; ++i)
{
int l, r;
scanf("%d%d", &l, &r);
queries[l].emplace_back(r, i);
}
SegmentTree seg(n, arr);
stack<int> mono;
for (int i = n; i >= 1; --i)
{
while (!mono.empty())
{
int j = mono.top();
seg.update(2 * j - i, n, arr[i] + arr[j]);
if (arr[j] <= arr[i])
mono.pop();
else
break;
}
mono.push(i);
for (auto [r, idx] : queries[i])
answer[idx] = seg.query(i, r);
}
for (int i = 1; i <= q; ++i)
printf("%lld\n", answer[i]);
}
