#include <bits/stdc++.h>
using namespace std;
typedef array<int, 3> Node; // 0/1/2: c/ab/abc
const int maxn = 1 << 19;
const int INF = 1e9;
int n, q;
int A[maxn];
vector<int> p[maxn];
vector<pair<int, int>> query[maxn];
struct segtree {
Node T[maxn << 1];
Node upd(const Node&x, const Node& y) {
return {max(x[0], y[0]), max(x[1], y[1]), max({x[1] + y[0], x[2], y[2]})};
}
void init() {
for (int i = maxn; i < maxn << 1; ++i) T[i] = {A[i - maxn], -INF, -INF};
for (int i = maxn - 1; i > 0; --i) T[i] = upd(T[2 * i], T[2 * i + 1]);
}
void update(int i, int v) {
i += maxn;
T[i][1] = max(T[i][1], v);
T[i][2] = max(T[i][2], T[i][1] + T[i][0]);
for (i >>= 1; i > 0; i >>= 1) {
T[i] = upd(T[2 * i], T[2 * i + 1]);
}
}
int get(int l, int r) {
Node L = {-INF, -INF, -INF};
Node R = L;
for (l += maxn, r += maxn; l < r; l >>= 1, r >>= 1) {
if (l & 1) {
L = upd(L, T[l]);
l++;
}
if (r & 1) {
r--;
R = upd(T[r], R);
}
}
return upd(L, R)[2];
}
} seg;
#define task "code"
int main() {
ios_base::sync_with_stdio(0); cin.tie(NULL);
// freopen(task".inp", "r", stdin);
// freopen(task".ans", "w", stdout);
cin >> n;
stack<int> st;
for (int i = 0; i < n; ++i) {
cin >> A[i];
while (!st.empty()) {
int j = st.top(), k = 2 * i - j;
if (k < n) p[j].push_back(k);
if (A[j] <= A[i]) st.pop();
else break;
}
st.push(i);
}
seg.init();
cin >> q;
vector<int> answer(q, 0);
for (int i = 0; i < q; ++i) {
int l, r; cin >> l >> r;
query[l - 1].emplace_back(r - 1, i);
}
for (int i = n - 1; i >= 0; --i) {
for (int j : p[i]) {
seg.update(j, A[i] + A[(i + j) / 2]); }
for (auto it : query[i]) {
answer[it.second] = seg.get(i, it.first + 1);
}
}
for (int i = 0; i < q; ++i) cout << answer[i] << "\n";
return 0;
}
