#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int unsigned int
using namespace std;
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("q.gir","r",stdin);
// freopen("q.cik","w",stdout);
int n;
cin>>n;
vector<int>arr(n);
for(int i=0;i<n;i++)cin>>arr[i];
int q;
cin>>q;
vector<vector<int>>rmq(n,vector<int>(n,0));
vector<vector<int>>ans(n,vector<int>(n,0));
for(int i=0;i<n;i++){
rmq[i][i]=arr[i];
for(int j=i+1;j<n;j++){
rmq[i][j]=max(rmq[i][j-1],arr[j]);
}
}
for(int i=0;i<n;i++){
for(int j=i+2;j<n;j++){
int diff=(j-i)/2;
int l=i+1,r=i+diff;
ans[i][j]=max(ans[i][j-1],arr[i]+arr[j]+rmq[l][r]);
}
}
while(q--){
int l,r;
cin>>l>>r;l--,r--;
int a=0;
for(int i=l;i<=r;i++){
a=max(a,ans[i][r]);
}
cout<<a<<"\n";
}
}
