#include <bits/stdc++.h>
#define N 5010
using namespace std;
int n, q, v[N], C[N][N], menor[N][N], dp[N][N];
int solve(int i, int j)
{
if(i > j) return 0;
if(dp[i][j] != -1) return dp[i][j];
return dp[i][j] = max({solve(i + 1, j), solve(i, j - 1), C[i][j]});
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>n;
for(int i = 1; i <= n; i++) cin>>v[i];
memset(dp, -1, sizeof dp);
for(int i = 1; i <= n; i++)
{
menor[i][i] = v[i];
for(int j = i + 1; j <= n; j++)
menor[i][j] = max(menor[i][j - 1], v[j]);
}
for(int i = 1; i <= n; i++)
{
for(int j = i + 1; j <= n; j++)
{
int mid = (i + j)/2;
C[i][j] = menor[i + 1][mid] + v[i] + v[j];
}
}
cin>>q;
for(int i = 1, l, r; i <= q; i++)
{
cin>>l>>r;
cout<<solve(l, r)<<"\n";
}
}
