#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define X first
#define Y second
const int N = 5e5 + 5;
const ll INF = 1e18;
struct Query {
int L, R, id;
};
int n, block_size;
int a[N], max_in_block[N / 1000 + 5];
ll f[N], lazy_block[N / 1000 + 5], best_in_block[N / 1000 + 5];
vector<pii> candidate_pairs;
void update_block(int pos, ll value) {
int block = pos / block_size;
int start = block * block_size;
int end = min((block + 1) * block_size - 1, n);
if (lazy_block[block] < value) {
lazy_block[block] = value;
best_in_block[block] = lazy_block[block] + max_in_block[block];
}
if (f[pos] < value) {
f[pos] = value;
best_in_block[block] = max(best_in_block[block], f[pos] + a[pos]);
}
for (int i = start; i <= end; i++) {
if (f[i] < lazy_block[block]) {
f[i] = lazy_block[block];
}
best_in_block[block] = max(best_in_block[block], f[i] + a[i]);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
block_size = sqrt(n);
for (int i = 1; i <= n; i++) {
cin >> a[i];
int block_idx = i / block_size;
if (a[i] > max_in_block[block_idx]) {
max_in_block[block_idx] = a[i];
}
}
deque<int> dq;
for (int i = n; i >= 1; i--) {
while (!dq.empty() && a[i] >= a[dq.back()]) {
candidate_pairs.push_back({i, dq.back()});
dq.pop_back();
}
if (!dq.empty()) {
candidate_pairs.push_back({i, dq.front()});
}
dq.push_front(i);
}
int q;
cin >> q;
vector<Query> queries(q);
vector<ll> ans(q, -INF);
for (int i = 0; i < q; i++) {
cin >> queries[i].L >> queries[i].R;
queries[i].id = i;
}
sort(queries.begin(), queries.end(), [](const Query& a, const Query& b) {
return a.L > b.L;
});
for (int i = 0; i <= n; i++) {
f[i] = -INF;
}
int num_blocks = (n + block_size - 1) / block_size;
for (int i = 0; i < num_blocks; i++) {
lazy_block[i] = -INF;
best_in_block[i] = -INF;
}
sort(candidate_pairs.begin(), candidate_pairs.end(), greater<pii>());
int ptr = 0;
for (const auto& query : queries) {
int L = query.L, R = query.R, id = query.id;
while (ptr < candidate_pairs.size() && candidate_pairs[ptr].X >= L) {
int x = candidate_pairs[ptr].X;
int y = candidate_pairs[ptr].Y;
ll s = a[x] + a[y];
int c_min = 2 * y - x;
ptr++;
if (c_min > n) continue;
int start_block = c_min / block_size;
int end_block = num_blocks - 1;
for (int block = start_block; block <= end_block; block++) {
int block_start = block * block_size;
int block_end = min((block + 1) * block_size - 1, n);
if (c_min <= block_start) {
if (s > lazy_block[block]) {
lazy_block[block] = s;
best_in_block[block] = max(best_in_block[block], lazy_block[block] + max_in_block[block]);
}
} else {
for (int j = max(c_min, block_start); j <= block_end; j++) {
if (s > f[j]) {
f[j] = s;
best_in_block[block] = max(best_in_block[block], f[j] + a[j]);
}
}
}
}
}
ll best = -INF;
int start_pos = L + 2;
if (start_pos > R) {
ans[id] = -INF;
continue;
}
int start_block = start_pos / block_size;
int end_block = R / block_size;
for (int block = start_block; block <= end_block; block++) {
int block_start = block * block_size;
int block_end = min((block + 1) * block_size - 1, n);
if (block_start >= start_pos && block_end <= R) {
best = max(best, best_in_block[block]);
} else {
for (int j = max(start_pos, block_start); j <= min(R, block_end); j++) {
if (f[j] < lazy_block[block]) {
f[j] = lazy_block[block];
}
best = max(best, f[j] + a[j]);
}
}
}
ans[id] = best;
}
for (int i = 0; i < q; i++) {
cout << ans[i] << '\n';
}
return 0;
}
