#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
const int N = 5e5 + 5, INF = 1e9;
int a[N], lm[N], rm[N], t[N * 4], up[N * 4], ans[N], mx[N * 4];
vector<pair<int, int>> ev[N], qr[N];
bool tup[N * 4];
void build(int v, int L, int R) {
if (L == R) {
mx[v] = a[L];
}
else {
int m = (L + R) >> 1;
build(v * 2, L, m);
build(v * 2 + 1, m + 1, R);
mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
}
}
void push(int v, int L, int R) {
if (tup[v]) {
if (L != R) {
up[v * 2] = up[v];
up[v * 2 + 1] = up[v];
tup[v * 2] = 1;
tup[v * 2 + 1] = 1;
}
t[v] = up[v] + mx[v];
tup[v] = 0;
}
}
void upd(int l, int r, int x, int v, int L, int R) {
push(v, L, R);
if (l > r)
return;
if (l == L && r == R) {
up[v] = x;
tup[v] = 1;
push(v, L, R);
}
else {
int m = (L + R) >> 1;
upd(l, min(m, r), x, v * 2, L, m);
upd(max(m + 1, l), r, x, v * 2 + 1, m + 1, R);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
}
int que(int l, int r, int v, int L, int R) {
push(v, L, R);
if (l > r)
return -INF;
if (l == L && r == R)
return t[v];
int m = (L + R) >> 1;
return max(que(l, min(m, r), v * 2, L, m),
que(max(m + 1, l), r, v * 2 + 1, m + 1, R));
}
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
build(1, 0, n - 1);
upd(0, n - 1, -INF, 1, 0, n - 1);
set<pair<int, int>> st;
st.insert({0, -INF});
st.insert({n, INF});
vector<int> v;
for (int i = 0; i < n; i++) {
while (!v.empty() && a[v.back()] < a[i])
v.pop_back();
lm[i] = v.empty() ? -1 : v.back();
v.push_back(i);
}
v.clear();
for (int i = n - 1; i >= 0; i--) {
while (!v.empty() && a[v.back()] < a[i])
v.pop_back();
rm[i] = v.empty() ? -1 : v.back();
v.push_back(i);
}
for (int i = 0; i < n; i++) {
if (lm[i] != -1)
ev[lm[i]].push_back({lm[i], i});
if (rm[i] != -1)
ev[i].push_back({i, rm[i]});
}
int q;
cin >> q;
for (int i = 0; i < q; i++) {
int l, r;
cin >> l >> r;
qr[l - 1].push_back({r - 1, i});
}
// for (int i = 0; i < n; i++) {
// for (auto p : ev[i]) {
// cout << p.first + 1 << " " << p.second + 1 << "\n";
// }
// }
for (int i = n - 1; i >= 0; i--) {
for (auto p : ev[i]) {
int x = p.second + p.second - p.first,
val = a[p.first] + a[p.second];
if (x >= n)
continue;
if (prev(st.lower_bound({x + 1, -1}))->second < val) {
auto it = st.lower_bound({x, -1});
while (it->second <= val) {
it++;
st.erase(prev(it));
}
upd(x, it->first - 1, val, 1, 0, n - 1);
st.insert(make_pair(x, val));
}
}
for (auto p : qr[i]) {
ans[p.second] = que(i, p.first, 1, 0, n - 1);
}
// for (auto p : st) {
// cout << p.first + 1 << " " << p.second << "\n";
// }
// cout << que(3, 3, 1, 0, n - 1) << "\n";
// cout << "\n";
}
for (int i = 0; i < q; i++) {
cout << ans[i] << "\n";
}
return 0;
}
