#include <bits/stdc++.h>
using namespace std;
const int N = 500000;
struct segtree {
segtree *left, *right;
int first, second, maxi;
void apply(int x) {
first = max(first, x);
maxi = max(maxi, first + second);
}
void push() {
left->apply(first);
right->apply(first);
}
void pull() {
second = max(left->second, right->second);
maxi = max({maxi, left->maxi, right->maxi});
}
segtree(int l, int r, int *a) {
first = maxi = INT_MIN;
if (l == r) {
second = a[l];
maxi = first + second;
} else {
int m = (l + r) / 2;
left = new segtree(l, m, a);
right = new segtree(m + 1, r, a);
pull();
}
}
void update(int a, int b, int x, int l, int r) {
if (a > b || b < l || r < a) {
return;
} else if (a <= l && r <= b) {
apply(x);
} else {
push();
int m = (l + r) / 2;
left->update(a, b, x, l, m);
right->update(a, b, x, m + 1, r);
pull();
}
}
int query(int a, int b, int l, int r) {
if (b < l || r < a) {
return INT_MIN;
} else if (a <= l && r <= b) {
return maxi;
} else {
push();
int m = (l + r) / 2;
return max(left->query(a, b, l, m), right->query(a, b, m + 1, r));
}
}
};
vector<array<int, 2>> queries[N];
int a[N], order[N], ans[N];
vector<int> pairs[N];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
iota(order, order + n, 0);
stable_sort(order, order + n, [&](int i, int j) {
return a[i] > a[j];
});
set<int> indices;
for (int i = 0; i < n; ++i) {
auto it = indices.lower_bound(order[i]);
if (it != indices.end()) {
pairs[order[i]].push_back(*it);
}
if (it != indices.begin()) {
pairs[*--it].push_back(order[i]);
}
indices.insert(order[i]);
}
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int l, r;
cin >> l >> r;
queries[l - 1].push_back({r - 1, i});
}
segtree *maxi = new segtree(0, n - 1, a);
for (int i = n - 1; i >= 0; --i) {
for (auto j : pairs[i]) {
maxi->update(2 * j - i, n - 1, a[i] + a[j], 0, n - 1);
}
for (auto [j, k] : queries[i]) {
ans[k] = maxi->query(i, j, 0, n - 1);
}
}
for (int i = 0; i < q; ++i) {
cout << ans[i] << "\n";
}
}
