#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second
const int SIZE = 1 << 15;
struct ST {
int A[2 * SIZE];
void update(int x, int v) {
for (x += SIZE; x; x >>= 1) A[x] = max(A[x], v);
}
int query(int s, int e) {
int ret = 0;
for (s += SIZE, e += SIZE; s <= e; s >>= 1, e >>= 1) {
if ( s & 1) ret = max(ret, A[s++]);
if (~e & 1) ret = max(ret, A[e--]);
}
return ret;
}
} seg;
int A[5005], X[5005][5005];
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int N; cin >> N;
if (N > 5000) assert(0);
for (int i = 1; i <= N; ++i) cin >> A[i], seg.update(i, A[i]);
for (int i = 2; i < N; ++i) {
for (int j = 1; j + i <= N; ++j) {
X[j][j + i] = max({X[j][j + i - 1], X[j + 1][j + i], seg.query(j + 1, j + i / 2) + A[j] + A[j + i]});
}
}
int Q; cin >> Q;
for (int i = 0; i < Q; ++i) {
int s, e; cin >> s >> e;
printf("%d\n", X[s][e]);
}
return 0;
}
