#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 <vector <int>> mx(n, vector <int> (n));
for (int l = 0; l < n; ++l) {
for (int r = 0; r < n; ++r) {
if (r > l) mx[l][r] = max(mx[l][r - 1], A[r]);
else mx[l][r] = A[r];
}
}
vector <vector <int>> dp(n, vector <int> (n));
for (int len = 3; len <= n; ++len) {
for (int l = 0; l + len <= n; ++l) {
int r = l + len - 1;
dp[l][r] = max(dp[l + 1][r], dp[l][r - 1]);
int m = (l + r) >> 1;
dp[l][r] = max(dp[l][r], A[l] + A[r] + mx[l + 1][m]);
}
}
int q;
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
--l, --r;
cout << dp[l][r] << '\n';
}
}
