#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5050;
#define MP make_pair
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int mx[N][N], ans[N][N];
int a[N];
void solve(){
int n;
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
for (int l = 1; l <= n; l++){
for (int r = l; r <= n; r++){
mx[l][r] = max(mx[l][r - 1], a[r]);
}
}
for (int i = 1; i <= n; i++){
for (int j = i + 2; j <= n; j++){
int k = (i + j) / 2;
ans[i][j] = a[i] + a[j] + mx[i + 1][k];
}
}
for (int i = n; i >= 1; i--){
for (int j = i; j <= n; j++){
ans[i][j] = max({ans[i][j], ans[i + 1][j], ans[i][j - 1]});
}
}
int q;
cin >> q;
while (q--){
int l, r;
cin >> l >> r;
cout << ans[l][r] << endl;
}
}
int main(){
ios_base::sync_with_stdio(false);
//freopen("output.txt", "w", stdout);
int tests = 1;
// cin >> tests;
while (tests--){
solve();
}
return 0;
}
