#include <bits/stdc++.h>
using namespace std;
#define intt long long
#define fi first
#define se second
const int N = 5e5+3;
intt a[N],n,m;
pair<intt,intt> b[N];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("CHONQUA.INP","r",stdin);
// freopen("CHONQUA.OUT","w",stdout);
cin>>n;
for(int i=1 ; i<=n;i++) cin>>a[i];
cin>>m;
for(int i=1 ; i<=m;i++){
cin>>b[i].fi>>b[i].se;
}
for(int i=1 ; i<=m;i++){
intt ans=0;
for(intt z=b[i].fi+2 ;z<=b[i].se;z++){
for(intt y=b[i].fi +1; y<z;y++){
for(intt x=b[i].fi; x<y;x++){
if(x+z-2*y >=0){
ans=max(ans , a[x]+a[y]+a[z]);
}
}
}
}
cout<<ans<<"\n";
}
}
