#include <bits/stdc++.h>
using namespace std;
int main() {
ios::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];
}
vector<int> stk;
vector<array<int, 2>> pos;
for (int i = 0; i < n; i++) {
while (!stk.empty() && a[stk.back()] < a[i]) {
stk.pop_back();
}
if (!stk.empty()) {
pos.push_back({stk.back(), i});
}
stk.push_back(i);
}
vector<int> s(n + 1);
for (int i = n - 1; i >= 0; i--) {
s[i] = max(s[i + 1], a[i]);
}
int q;
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
l--; r--;
int ans = 0;
for (auto [i, j] : pos) {
int k = 2 * j - i;
if (k > j && k < n && l <= i && k <= r) {
ans = max(ans, a[i] + a[j] + s[k]);
}
}
cout << ans << '\n';
}
return 0;
}
