#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cmath>
#include <climits>
using namespace std;
class SegmentTree {
private:
int n;
vector<int> data;
public:
SegmentTree(int size) {
n = 1;
while (n < size) n <<= 1;
data.assign(2 * n, -1e9);
}
void update(int pos, int val) {
pos += n;
if (val > data[pos]) {
data[pos] = val;
}
pos >>= 1;
while (pos >= 1) {
int new_val = max(data[2 * pos], data[2 * pos + 1]);
if (new_val == data[pos]) break;
data[pos] = new_val;
pos >>= 1;
}
}
int query(int l, int r) {
l += n;
r += n;
int res = -1e9;
while (l <= r) {
if (l % 2 == 1) res = max(res, data[l++]);
if (r % 2 == 0) res = max(res, data[r--]);
l >>= 1;
r >>= 1;
}
return res;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<int> A(N);
for (int i = 0; i < N; ++i) {
cin >> A[i];
}
int Q;
cin >> Q;
vector<pair<int, int>> queries(Q);
for (int i = 0; i < Q; ++i) {
cin >> queries[i].first >> queries[i].second;
queries[i].first--;
queries[i].second--;
}
int LOG = log2(N) + 1;
vector<vector<pair<int, int>>> st(LOG, vector<pair<int, int>>(N));
for (int i = 0; i < N; ++i) {
st[0][i] = {A[i], i};
}
for (int j = 1; j < LOG; ++j) {
for (int i = 0; i + (1 << j) <= N; ++i) {
st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
}
auto query_range_max = [&](int l, int r) {
if (l > r) return make_pair(-1e9, -1);
int k = log2(r - l + 1);
return max(st[k][l], st[k][r - (1 << k) + 1]);
};
vector<vector<int>> next_greater(N);
stack<int> s;
for (int i = 0; i < N; ++i) {
while (!s.empty() && A[s.top()] < A[i]) {
next_greater[s.top()].push_back(i);
s.pop();
}
if (!s.empty()) {
next_greater[s.top()].push_back(i);
}
s.push(i);
}
vector<tuple<int, int, int>> events;
for (int i = 0; i < N; ++i) {
for (int j : next_greater[i]) {
int k_low = 2 * j - i;
if (k_low < N) {
auto [max_val, max_idx] = query_range_max(k_low, N - 1);
int total = A[i] + A[j] + max_val;
events.emplace_back(max_idx, i, total);
}
}
}
sort(events.begin(), events.end());
vector<tuple<int, int, int>> sorted_queries;
for (int i = 0; i < Q; ++i) {
sorted_queries.emplace_back(queries[i].second, queries[i].first, i);
}
sort(sorted_queries.begin(), sorted_queries.end());
SegmentTree seg_tree(N);
vector<int> ans(Q, -1e9);
int event_ptr = 0;
for (auto [R, L, idx] : sorted_queries) {
while (event_ptr < events.size() && get<0>(events[event_ptr]) <= R) {
auto [k, i, val] = events[event_ptr];
seg_tree.update(i, val);
event_ptr++;
}
ans[idx] = seg_tree.query(L, N - 1);
}
for (int i = 0; i < Q; ++i) {
cout << ans[i] << '\n';
}
return 0;
}
