#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int Inf = 2e9;
struct Node {
int sum, val, mx;
Node() {
sum = mx = -Inf;
val = 0;
}
Node operator +(const Node &other) const {
Node res;
res.sum = max(sum, other.sum);
res.val = max(val, other.val);
res.mx = max(mx, other.mx);
res.mx = max(res.mx, sum + other.val);
return res;
}
};
const int N = 5e5 + 7;
Node t[4 * N];
void build(int l, int r, int v, vector <int> &a) {
if (l == r) {
t[v].val = a[l];
} else {
int m = (l + r) >> 1;
build(l, m, 2 * v + 1, a);
build(m + 1, r, 2 * v + 2, a);
t[v] = t[2 * v + 1] + t[2 * v + 2];
}
}
void modify(int ind, int sm, int l, int r, int v) {
if (l == r) {
t[v].sum = max(t[v].sum, sm);
t[v].mx = t[v].val + t[v].sum;
} else {
int m = (l + r) >> 1;
if (ind <= m) modify(ind, sm, l, m, 2 * v + 1);
else modify(ind, sm, m + 1, r, 2 * v + 2);
t[v] = t[2 * v + 1] + t[2 * v + 2];
}
}
Node get(int ql, int qr, int l, int r, int v) {
if (qr < l || r < ql) return Node();
if (ql <= l && r <= qr) return t[v];
int m = (l + r) >> 1;
return get(ql, qr, l, m, 2 * v + 1) + get(ql, qr, m + 1, r, 2 * v + 2);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int n;
cin >> n;
vector <int> A(n);
for (int i = 0; i < n; ++i) {
cin >> A[i];
}
vector <int> L(n, -1), R(n, n);
vector <pair <int, int>> st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && st.back().first < A[i]) st.pop_back();
if (!st.empty()) L[i] = st.back().second;
st.push_back({A[i], i});
}
st.clear();
for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && st.back().first <= A[i]) st.pop_back();
if (!st.empty()) R[i] = st.back().second;
st.push_back({A[i], i});
}
vector <pair <int, int>> intr;
for (int i = 0; i < n; ++i) {
int j = L[i];
if (j != -1) {
intr.push_back({j, i});
}
j = R[i];
if (j != n) {
intr.push_back({i, j});
}
}
sort(intr.begin(), intr.end());
intr.resize(unique(intr.begin(), intr.end()) - intr.begin());
build(0, n - 1, 0, A);
vector <vector <int>> who(n);
for (auto p : intr) {
who[p.first].push_back(p.second);
}
int q;
cin >> q;
vector <int> ql(q), qr(q);
vector <int> ans(q);
vector <vector <int>> qrs(n);
for (int i = 0; i < q; ++i) {
cin >> ql[i] >> qr[i];
--ql[i], --qr[i];
qrs[ql[i]].push_back(i);
}
for (int i = n - 1; i >= 0; --i) {
for (int j : who[i]) {
if (j + j - i < n) {
modify(j + j - i, A[i] + A[j], 0, n - 1, 0);
}
}
for (int id : qrs[i]) {
ans[id] = get(ql[id], qr[id], 0, n - 1, 0).mx;
}
}
for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
}
