#include <bits/stdc++.h>
using namespace std;
#define Task ""
struct __Init__ {
__Init__() {
cin.tie(nullptr)->sync_with_stdio(false);
if (fopen(Task".inp", "r")) {
freopen(Task".inp", "r", stdin);
freopen(Task".out", "w", stdout); }
}
} __init__;
using ll = long long;
#ifdef LOCAL
#define debug(x) cerr << "[" #x " = " << x << "]\n";
#else
#define debug(...)
#endif // LOCAL
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fi first
#define se second
#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)
template<class C> int isz(const C& c) { return c.size(); }
template<class T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }
constexpr int eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;
// =============================================================================
constexpr int maxN = 5e5 + 5;
int n, nq;
int a[maxN];
struct Sub2 {
static constexpr int maxN = 5005;
int dp[maxN][maxN];
void solve() {
For (i, 1, n - 2) {
int p = i + 1;
int mx = a[p];
For (j, i + 2, n) {
while (p - i + 1 <= j - p - 1) {
chmax(mx, a[++p]);
}
dp[i][j] = a[i] + a[j] + mx;
}
}
For (len, 4, n) {
For (i, 1, n - len + 1) {
int j = i + len - 1;
chmax(dp[i][j], max(dp[i][j - 1], dp[i + 1][j]));
}
}
cin >> nq;
Rep (_, nq) {
int l, r; cin >> l >> r;
cout << dp[l][r] << '\n';
}
}
};
signed main() {
cin >> n;
For (i, 1, n) cin >> a[i];
#define SUB(x) \
Sub##x* sol = new Sub##x{}; \
sol->solve(); delete sol
if (n <= 5000) {
SUB(2);
}
}
/*
*/
