#include <bits/stdc++.h>
using namespace std;
struct maxseg
{
vector<int> tree;
maxseg(int siz){tree.resize(1<<((int)ceil(log2(siz))+1));}
int init(int s, int e, int node, vector<int> &arr)
{
if(s==e) return tree[node] = arr[s];
return tree[node] = max(init(s, (s+e)/2, 2*node, arr), init((s+e)/2+1, e, 2*node+1, arr));
}
void upd(int s, int e, int node, int idx, int val)
{
if(e<idx|idx<s) return;
if(s==e){
tree[node] = val; return;
}
upd(s, (s+e)/2, 2*node, idx, val); upd((s+e)/2+1, e, 2*node+1, idx, val);
tree[node] = max(tree[2*node], tree[2*node+1]);
}
int query(int s, int e, int node, int l, int r)
{
if(e<l||r<s) return 0;
if(l<=s&&e<=r) return tree[node];
return max(query(s, (s+e)/2, 2*node, l, r), query((s+e)/2+1, e, 2*node+1, l, r));
}
};
int dp[5005][5005];
int dp2[5005][5005];
int dp3[5005][5005];
int a[5005];
signed main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n; cin >> n;
vector<int> tmp(n+1);
for (int i = 1; i <= n; i++){cin >> a[i]; tmp[i] = a[i];}
maxseg seg(n);
seg.init(1, n, 1, tmp);
for (int i = 1; i <= n; i++) {
for (int j = i + 2; j <= n; j++) {
//사잇값 범위 i + 1 ~ (i + j) / 2
dp[i][j] = a[i] + a[j] + seg.query(1, n, 1, i + 1, (i + j) / 2);
}
}
for (int i = n; i >= 1; i--) {
for (int j = i - 2; j >= 1; j--) {
dp2[j][i] = max(dp2[j+1][i], dp[j][i]);
}
}
for (int i = 1; i <= n; i++) {
for (int j = i + 2; j <= n; j++) {
dp3[i][j] = max(dp3[i][j-1], dp2[i][j]);
}
}
int Q; cin >> Q;
while (Q--) {
int l, r; cin >> l >> r;
cout << dp3[l][r] << '\n';
}
}
