#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MXN = 5e3;
int n , q;
ll a[MXN + 5] , maxVals[MXN + 5][MXN + 5];
ll dp[MXN + 5][MXN + 5];
void precompute(){
for (int i = 1; i <= n ;i++){
for (int j = i; j <= n ;j++){
maxVals[i][j] = max(maxVals[i][j - 1] , a[j]);
}
}
for (int l = n - 2;l >= 1; l--){
for (int r = l + 2 ; r <= n ;r++){
dp[l][r] = max({dp[l + 1][r] , dp[l][r - 1] , a[l] + a[r] + maxVals[l + 1][(r + l) / 2]});
}
}
}
signed main() {
cin.tie(0)->ios_base::sync_with_stdio(0);
cin >> n;
for (int i = 1; i<= n ;i++) cin >> a[i];
precompute();
cin >> q;
while(q--){
int l , r; cin >> l >> r;
cout << dp[l][r] <<'\n';
}
}
//aaca
//aaac
