#define ll long long
#include <bits/stdc++.h>
using namespace std;
ll left(ll i)
{return 2*i;}
ll right(ll i)
{return 2*i+1;}
ll query(vector<ll>& s, ll i, ll a, ll b, ll l, ll r)
{
if(l <= a && b <= r)
return s[i];
if(r < a || b < l)
return 0;
ll mid = (a+b)/2;
return max(query(s, left(i), a, mid, l, r), query(s, right(i), mid+1, b, l, r));
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll n;
cin>>n;
vector<ll> a(n);
for(ll& i : a)
cin>>i;
ll segnodes = 1;
while(2*n > segnodes)
segnodes *= 2;
vector<ll> s(segnodes, 0);
for(ll i = 0; i < n; i++)
s[segnodes/2 + i] = a[i];
for(ll i = segnodes/2 - 1; i > 0; i--)
s[i] = max(s[left(i)], s[right(i)]);
vector<vector<ll>> dp(n, vector<ll> (n, 0));
for(ll i = 0; i+2 < n; i++)
dp[i][i+2] = a[i]+a[i+1]+a[i+2];
for(ll k = 3; k < n; k++)
{
for(ll i = 0; i+k < n; i++)
{
ll j = i+k;
dp[i][j] = max(dp[i][j-1], dp[i+1][j]);
dp[i][j] = max(dp[i][j], (a[i]+a[j]+query(s, 1, 1, segnodes/2, 1+i+1, 1+i+((ll) k/2))));
}
}
ll q;
cin>>q;
while(q--)
{
ll l, r;
cin>>l>>r;
l--; r--;
cout<<dp[l][r]<<"\n";
}
}
