#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 1e6 + 26;
const ll INF = 1e18;
int n, m, a[MAXN];
ll ans[MAXN];
vector<pair<int, int>> candidates;
vector<tuple<int, int, int>> queries;
struct SegmentTree {
ll tree[4 * MAXN], lazy[4 * MAXN];
ll pr[4 * MAXN]; // max a[z] in segment
void build(int k, int l, int r) {
lazy[k] = -INF;
if (l == r) {
tree[k] = -INF;
pr[k] = a[l];
return;
}
int m = (l + r) >> 1;
build(2*k, l, m);
build(2*k+1, m+1, r);
tree[k] = max(tree[2*k], tree[2*k+1]);
pr[k] = max(pr[2*k], pr[2*k+1]);
}
void push(int k, int l, int r) {
if (lazy[k] != -INF) {
tree[k] = max(tree[k], pr[k] + lazy[k]);
if (l != r) {
lazy[2*k] = max(lazy[2*k], lazy[k]);
lazy[2*k+1] = max(lazy[2*k+1], lazy[k]);
}
lazy[k] = -INF;
}
}
void update(int k, int l, int r, int u, int v, ll f) {
push(k, l, r);
if (l > v || r < u) return;
if (l >= u && r <= v) {
lazy[k] = f;
push(k, l, r);
return;
}
int m = (l + r) >> 1;
update(2*k, l, m, u, v, f);
update(2*k+1, m+1, r, u, v, f);
tree[k] = max(tree[2*k], tree[2*k+1]);
}
ll query(int k, int l, int r, int u, int v) {
push(k, l, r);
if (l > v || r < u) return -INF;
if (l >= u && r <= v) return tree[k];
int m = (l + r) >> 1;
return max(query(2*k, l, m, u, v), query(2*k+1, m+1, r, u, v));
}
} seg;
void find_pairs() {
stack<int> st;
for (int j = 1; j <= n; j++) {
while (!st.empty() && a[st.top()] < a[j]) {
int i = st.top(); st.pop();
candidates.push_back({i, j});
}
if (!st.empty()) {
candidates.push_back({st.top(), j});
}
st.push(j);
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> m;
for (int i = 0; i < m; i++) {
int l, r; cin >> l >> r;
queries.emplace_back(l, r, i);
}
find_pairs();
seg.build(1, 1, n);
// Sort queries by l descending
sort(queries.rbegin(), queries.rend());
// Sort candidates by i descending
sort(candidates.rbegin(), candidates.rend());
int j = 0;
for (auto [l, r, idx] : queries) {
while (j < candidates.size() && candidates[j].first >= l) {
int i = candidates[j].first, j_val = candidates[j].second;
int z_min = 2 * j_val - i;
if (z_min <= n) {
seg.update(1, 1, n, z_min, n, a[i] + a[j_val]);
}
j++;
}
ans[idx] = seg.query(1, 1, n, l, r);
}
for (int i = 0; i < m; i++) cout << ans[i] << "\n";
}
