#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define len(x) (ll)x.size()
const ll inf = 1e9, infl = 1e18;
const ll MOD = 1e9 + 7;
const ll maxn = 5e3 + 5;
ll n, m, k = 0;
ll a[maxn], tree[maxn * 4], cv[maxn][maxn];
void build(ll l = 1, ll r = n, ll v = 1){
if(l == r){
tree[v] = a[l];
return;
}
ll md = (l + r) >> 1;
build(l, md, v << 1);
build(md + 1, r, v << 1 | 1);
tree[v] = max(tree[v << 1], tree[v << 1 | 1]);
}
ll get(ll _l, ll _r, ll l = 1, ll r = n, ll v = 1){
bool in = _l <= l and r <= _r;
bool ot = _l <= r and l <= _r;
if(in) return tree[v];
if(ot){
ll md = (l + r) >> 1;
return max(get(_l, _r, l, md, v << 1), get(_l, _r, md + 1, r, v << 1 | 1));
}
return -infl;
}
void _() {
cin >> n;
for(ll i = 1; i <= n; i ++){
cin >> a[i];
}
build();
for(ll i = 1; i <= n; i ++){
cv[i][i] = cv[i][i + 1] = -infl;
for(ll j = i + 2; j <= n; j ++){
ll md = i + (j - i) / 2;
// cout << i << ' ' << md << ' ' << j << '\n';
cv[i][j] = a[i] + a[j] + get(i + 1, md);
}
}
for(ll d = 1; d <= n; d ++){
for(ll i = n; i >= 1; i --){
cv[i][i + d] = max(cv[i][i + d], cv[i + 1][i + d]);
cv[i][i + d] = max(cv[i][i + d], cv[i][i + d - 1]);
}
}
cin >> m;
for(ll i = 1, l, r; i <= m; i ++){
cin >> l >> r;
cout << cv[l][r] << '\n';
}
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
ll t = 1;
// cin >> t;
while(t --) _();
}
