#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define ALL(x) (x).begin(), (x).end()
#define nqthanhhai signed main()
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp","r", stdin); freopen(name".out", "w", stdout); }
#define el '\n'
#define ll long long
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define fi first
#define se second
const ll ar=1e6;
using namespace std;
ll n,l,r,t,a[ar],res=0;
nqthanhhai
{
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
FOR (i,1,n){
cin>>a[i];
}
cin>>t;
while (t--){
res=0;
cin>> l >>r ;
FOR (x,l,r-2){
FOR (y, x+1, r-1){
FOR (z, y+(y-x),r){
res=max(res,a[x]+a[y]+a[z]);
}
}
}
cout<<res<<el;
}
cerr<<"Time elapsed: "<<TIME<<"s. \n";
return 0;
}
