#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5010;
int N;
int A[MAXN];
int best[MAXN][MAXN];
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> A[i];
}
for (int l = 0; l < N; l++) {
int maxval = 0;
for (int r = l+2; r <= N; r++) {
if ((r-l) % 2 == 1) {
maxval = max(maxval, A[l + (r-l-1) / 2]);
}
best[l][r] = A[l] + A[r-1] + maxval;
}
}
for (int l = N-1; l >= 0; l--) {
for (int r = l+2; r <= N; r++) {
if (r+1 <= N) {
best[l][r+1] = max(best[l][r+1], best[l][r]);
}
if (l-1 >= 0) {
best[l-1][r] = max(best[l-1][r], best[l][r]);
}
}
}
int Q; cin >> Q;
while (Q--) {
int l, r; cin >> l >> r; l--;
cout << best[l][r] << '\n';
}
return 0;
}
