#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int n;
cin >> n;
vector <int> A(n);
for (int i = 0; i < n; ++i) {
cin >> A[i];
}
vector <int> sufMax(n);
for (int i = n - 1; i >= 0; --i) {
sufMax[i] = A[i];
if (i + 1 < n) sufMax[i] = max(sufMax[i], sufMax[i + 1]);
}
vector <int> L(n, -1), R(n, n);
vector <pair <int, int>> st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && st.back().first < A[i]) st.pop_back();
if (!st.empty()) L[i] = st.back().second;
st.push_back({A[i], i});
}
st.clear();
for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && st.back().first <= A[i]) st.pop_back();
if (!st.empty()) R[i] = st.back().second;
st.push_back({A[i], i});
}
int ans = 0;
auto check = [&] (int i, int j) {
int minK = j + j - i;
if (minK < n) {
ans = max(ans, A[i] + A[j] + sufMax[minK]);
}
};
for (int i = 0; i < n; ++i) {
int j = L[i];
if (j != -1) check(j, i);
j = R[i];
if (j != n) check(i, j);
}
int q;
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
--l, --r;
cout << ans << '\n';
}
}
