#include <iostream>
#include <vector>
#include <stack>
using namespace std;
#define ll long long
const int N = 5e5 + 10;
int n, m, a[N];
ll ans[N];
vector <int> v[N], Q[N];
stack <int> st;
struct query {
int l, r;
} q[N];
struct SEG {
struct node {
ll one, two, val;
node operator + (const node &o) const {
node res;
res.one = max(one, o.one);
res.two = max(two, o.two);
res.val = max(max(val, o.val), two + o.one);
return res;
}
} st[N << 2];
void build(int l, int r, int id) {
if (l == r) {
st[id].one = a[l];
st[id].two = st[id].val = 0;
return;
}
int mid = (l + r) >> 1;
build(l, mid, id << 1);
build(mid + 1, r, id << 1 | 1);
st[id] = st[id << 1] + st[id << 1 | 1];
}
void update(int l, int r, int u, ll VAL, int id) {
if (l == r) {
st[id].two = max(st[id].two, VAL);
st[id].val = st[id].one + st[id].two;
return;
}
int mid = (l + r) >> 1;
if (u <= mid) update(l, mid, u, VAL, id << 1);
else update(mid + 1, r, u, VAL, id << 1 | 1);
st[id] = st[id << 1] + st[id << 1 | 1];
}
node get(int l, int r, int u, int v, int id) {
if (l > v || r < u) return st[0];
if (l >= u && r <= v) return st[id];
int mid = (l + r) >> 1;
return get(l, mid, u, v, id << 1) + get(mid + 1, r, u, v, id << 1 | 1);
}
} seg;
int main() {
cin.tie(0); cout.tie(0);
ios_base::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
while (!st.empty() && a[st.top()] <= a[i]) {
v[st.top()].push_back(i);
st.pop();
}
if (!st.empty()) v[st.top()].push_back(i);
st.push(i);
}
cin >> m;
for (int i = 1; i <= m; ++i) {
cin >> q[i].l >> q[i].r;
Q[q[i].l].push_back(i);
}
seg.build(1, n, 1);
for (int i = n; i >= 1; --i) {
for (int z: v[i]) {
int nxt = 2 * z - i;
if (nxt <= n) {
seg.update(1, n, nxt, a[i] + a[z], 1);
}
}
for (int z: Q[i]) {
SEG::node cur = seg.get(1, n, q[z].l, q[z].r, 1);
ans[z] = cur.val;
}
}
for (int i = 1; i <= m; ++i) {
cout << ans[i] << "\n";
}
return 0;
}
