//雪花飄飄北風嘯嘯
//天地一片蒼茫
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
struct sparse{
long long ST[100005][20];
sparse(){}
long long func(long long i,long long j){return max(i,j);}
///change this
void build(int n,long long arr[]){ ///build sparse table
for (int x=0;x<n;x++){
ST[x][0]=arr[x];
}
int j=1,logj=1;
while (j<=(n>>1)){
for (int x=0;x<=(n-(j<<1));x++){
ST[x][logj]=func(ST[x][logj-1],ST[x+j][logj-1]);
}
j<<=1;
logj++;
}
}
long long query(int i, int j){ ///in range [i,j]
j=j-i+1;
int row=31-__builtin_clz(j);
j-=1<<row;
return func(ST[i][row],ST[i+j][row]);
}
} ST;
int n,q;
ll arr[200005];
ll memo[5005][5005];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
rep(x,0,n) cin>>arr[x];
ST.build(n,arr);
rep(x,2,n){
rep(l,0,n-x){
int r=l+x;
//cout<<l<<" "<<r<<endl;
memo[l][r]=max(memo[l+1][r],memo[l][r-1]);
memo[l][r]=max(memo[l][r],arr[l]+arr[r]+ST.query(l+1,l+x/2));
}
}
cin>>q;
int l,r;
while (q--){
cin>>l>>r;
l--,r--;
cout<<memo[l][r]<<endl;
}
}
