#include <bits/stdc++.h>
using namespace std;
#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
#ifdef ngu
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
#endif
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int q;
cin >> q;
vector<vector<pair<int, int>>> qry(n);
vector<vector<int>> g(n);
for (int i = 0; i < q; ++i) {
int l, r;
cin >> l >> r;
l--, r--;
qry[l].emplace_back(r, i);
}
vector<int> st;
for (int i = 0; i < n; ++i) {
while (st.size() && a[st.back()] < a[i]) {
st.pop_back();
}
if (st.size()) {
g[st.back()].emplace_back(i);
}
st.emplace_back(i);
}
while (st.size()) {
st.pop_back();
}
for (int i = n - 1; ~i; --i) {
while (st.size() && a[st.back()] <= a[i]) {
st.pop_back();
}
if (st.size()) {
g[i].emplace_back(st.back());
}
st.emplace_back(i);
}
const int INF = int(1e9);
vector<int> s(4 << __lg(n), -INF);
auto lz = s;
auto mx = s;
auto app = [&](int id, int x) {
lz[id] = max(lz[id], x);
s[id] = max(s[id], x + mx[id]);
};
auto psh = [&](int id) {
app(id * 2, lz[id]);
app(id * 2 + 1, lz[id]);
lz[id] = -INF;
};
auto updP = [&](int i) {
int id = 1, l = 0, r = n - 1;
while (l ^ r) {
int md = (l + r) / 2;
if (lz[id] != -INF) {
psh(id);
}
id *= 2;
if (i <= md) {
r = md;
} else {
l = md + 1;
id += 1;
}
}
mx[id] = a[i];
while (id > 1) {
id /= 2;
mx[id] = max(mx[id * 2], mx[id * 2 + 1]);
}
};
auto upd = [&](int i, int x) {
int id = 1, l = 0, r = n - 1;
while (l ^ r) {
int md = (l + r) / 2;
if (lz[id] != -INF) {
psh(id);
}
id *= 2;
if (i - 1 <= md) {
app(id + 1, x);
r = md;
} else {
id += 1;
l = md + 1;
}
}
while (id > 1) {
id /= 2;
s[id] = max(s[id * 2], s[id * 2 + 1]);
}
};
auto get = [&](int i) {
int id = 1, l = 0, r = n - 1;
int res = -INF;
while (l ^ r) {
int md = (l + r) / 2;
if (lz[id] != -INF) {
psh(id);
}
id *= 2;
if (i <= md) {
r = md;
} else {
res = max(res, s[id]);
l = md + 1;
id += 1;
}
}
return max(res, s[id]);
};
vector<int> res(q);
for (int l = n - 1; ~l; --l) {
updP(l);
for (int r : g[l]) {
upd(2 * r - l, a[l] + a[r]);
}
for (auto [r, id] : qry[l]) {
res[id] = get(r);
}
}
for (int i = 0; i < q; ++i) {
cout << res[i] << "\n";
}
}
