#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
srand((unsigned)time(NULL));
ios::sync_with_stdio(false);
std::cin.tie(0);
int N;
cin>>N;
vector<int> A(N);
for(int i=0;i<N;i++) cin>>A[i];
vector<vector<int>> S(N,vector<int>(N));
vector<vector<int>> T(N,vector<int>(N));
for(int i=0;i<N;i++){
int ma = 0;
for(int j=i+2;j<N;j++){
if((j-i)%2 == 0) ma = max(ma,A[(i+j)/2]);
S[i][j] = ma+A[i]+A[j];
}
}
for(int i=0;i<N;i++)for(int j=0;j<N;j++){
if(j != 0) S[i][j] = max(S[i][j],S[i][j-1]);
}
for(int r=2;r<N;r++)for(int l=r-2;l>=0;l--){
S[l][r] = max(S[l][r],S[l+1][r]);
}
int Q;
cin>>Q;
while(Q--){
int l,r;
cin>>l>>r;
l--;
r--;
cout<<S[l][r]<<endl;
}
}
