#include "bits/stdc++.h"
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif
const int N = 5e5 + 5;
struct node {
int ans;
int ab, c;
};
node seg[N * 2];
node merge(const node& lx, const node& rx) {
node ret;
ret.ans = max(lx.ans, rx.ans);
if (lx.ab) {
ret.ans = max(ret.ans, lx.ab + rx.c);
}
ret.ab = max(lx.ab, rx.ab);
ret.c = max(lx.c, rx.c);
return ret;
}
void build(int nd, int l, int r, const vector<int>& c) {
if (l == r) {
seg[nd].c = c[l];
return;
}
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
build(nd + 1, l, mid, c);
build(rs, mid + 1, r, c);
seg[nd].c = max(seg[nd + 1].c, seg[rs].c);
}
void upd(int nd, int l, int r, int p, int v) {
if (l == r) {
seg[nd].ab = max(seg[nd].ab, v);
seg[nd].ans = max(seg[nd].ans, seg[nd].ab + seg[nd].c);
return;
}
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
if (p <= mid) {
upd(nd + 1, l, mid, p, v);
} else {
upd(rs, mid + 1, r, p, v);
}
seg[nd] = merge(seg[nd + 1], seg[rs]);
}
node qry(int nd, int l, int r, int s, int e) {
if (l >= s && r <= e) {
return seg[nd];
}
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
node ret;
if (mid >= e) {
ret = qry(nd + 1, l, mid, s, e);
} else {
if (mid < s) {
ret = qry(rs, mid + 1, r, s, e);
} else {
ret = merge(qry(nd + 1, l, mid, s, e), qry(rs, mid + 1, r, s, e));
}
}
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
build(0, 0, n - 1, a);
vector<vector<pair<int, int>>> vec(n);
stack<int> stk;
for (int i = 0; i < n; ++i) {
while (!stk.empty() && a[stk.top()] < a[i]) {
if (2 * i - stk.top() < n) {
vec[stk.top()].emplace_back(2 * i - stk.top(), a[i] + a[stk.top()]);
}
stk.pop();
}
if (!stk.empty()) {
if (2 * i - stk.top() < n) {
vec[stk.top()].emplace_back(2 * i - stk.top(), a[i] + a[stk.top()]);
}
}
stk.push(i);
}
int q;
cin >> q;
vector<int> ans(q);
vector<vector<pair<int, int>>> qs(n);
for (int i = 0; i < q; ++i) {
int l, r;
cin >> l >> r;
--l, --r;
qs[l].emplace_back(r, i);
}
for (int l = n - 1; l >= 0; --l) {
for (auto [p, s] : vec[l]) {
upd(0, 0, n - 1, p, s);
}
for (auto [r, i] : qs[l]) {
ans[i] = qry(0, 0, n - 1, 0, r).ans;
}
}
for (int i = 0; i < q; ++i) {
cout << ans[i] << '\n';
}
return 0;
}
