#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
//#define int ll
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
int n,m;
const int N=1e5+5;
int dp[5005][5005];
int tree[5005*4];
int a[5005];
void build(int x, int l, int r) {
if(l==r) {
tree[x]=a[l];
return;
}
int md=(l+r)/2;
build(2*x,l,md);
build(2*x+1,md+1,r);
tree[x]=max(tree[2*x],tree[2*x+1]);
}
int query(int lx, int rx, int x, int l, int r) {
if(l>rx || r<lx) return 0;
if(lx<=l && r<=rx) return tree[x];
int md=(l+r)/2;
return max(query(lx,rx,2*x,l,md),query(lx,rx,2*x+1,md+1,r));
}
void solve() {
int n;cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
for(int j=2;j<=n;j++){
for(int i=1;i<=n;i++) {
if(i+j>n) break;
dp[i][i+j]=a[i]+a[i+j]+query(i+1,(i+i+j)/2,1,1,n);
dp[i][i+j]=max({dp[i][i+j],dp[i+1][i+j],dp[i][i+j-1]});
//cout<<i<<' '<<i+j<<' '<<dp[i][i+j]<<endl;
}
}
int q;cin>>q;
while(q--) {
int l,r;cin>>l>>r;
cout<<dp[l][r]<<endl;;
}
}
signed main(){
int t=1;//cin>>t;
while(t--){
solve();
}
}
//#endif
