#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using vi = vector<ll>;
using vvi = vector<vi>;
const ll mod = 1000000007ll;
ll n, mx[5050][5050], dp[5050][5050];
vi a;
ll getmax(int l, int r) {
l = max(l, 1);
r = min(r, (int)n);
if(l > r) return 0;
if(mx[l][r]) return mx[l][r];
if(l == r) return mx[l][r] = a[l];
return mx[l][r] = max(getmax(l, r-1), a[r]);
}
ll get(int l, int r) {
if(r-l<2) return 0;
if(dp[l][r] != -1) return dp[l][r];
dp[l][r] = a[l]+a[r]+getmax(l+1, (r+l)/2);
dp[l][r] = max({dp[l][r], get(l+1, r), get(l, r-1)});
return dp[l][r];
}
int main() {
ios::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
memset(dp, -1, sizeof dp);
memset(mx, 0, sizeof mx);
cin >> n;
a.resize(n+1);
for(int i = 1; i <= n; i++) cin >> a[i];
int q, l, r;
cin >> q;
while(q--) {
cin >> l >> r;
cout << get(l, r) << "\n";
}
}
