#include<bits/stdc++.h>
using namespace std;
const int N=5005;
int sp[13][N],dp[N][N];
void build(int n){
for(int j=1;j<13;j++){
for(int i=0;i+(1<<j)<=n;i++){
sp[j][i]=max(sp[j-1][i],sp[j-1][i+(1<<(j-1))]);
}
}
}
int RMQ(int l,int r){
int sz=__lg(r-l+1);
return max(sp[sz][l],sp[sz][r-(1<<sz)+1]);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
for(int i=0;i<n;i++)cin>>sp[0][i];
build(n);
for(int sz=2;sz<n;sz++){
for(int i=0;i+sz<n;i++){
dp[i][i+sz]=sp[0][i]+sp[0][i+sz]+RMQ(i+1,(i+sz+i)/2);
dp[i][i+sz]=max({dp[i][i+sz],dp[i+1][i+sz],dp[i][i+sz-1]});
}
}
int q;
cin>>q;
while(q--){
int l,r;
cin>>l>>r;
l--;r--;
cout<<dp[l][r]<<"\n";
}
return 0;
}
