#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef pair<ull, ull> pull;
typedef pair<ld, ld> pld;
ll sfunc(pii a, pii b){
return a.ss < b.ss;
}
vector<pii> merge(vector<pii> v1, vector<pii> v2){
vector<pii> ret;
ll i = 0, j = 0;
while(ret.size() < 20 && (i < v1.size() || j < v2.size())){
if(i == v1.size())
ret.pb(v2[j++]);
else if(j == v2.size())
ret.pb(v1[i++]);
else if(v1[i].ff > v2[j].ff)
ret.pb(v1[i++]);
else
ret.pb(v2[j++]);
}
return ret;
}
ll a[500009];
vector<pii> seg[2000000];
void build(ll v, ll tl, ll tr){
if(tl == tr){
seg[v].pb(mp(a[tl], tl));
return;
}
build(2*v, tl, (tl+tr)/2);
build(2*v+1, (tl+tr)/2+1, tr);
seg[v] = merge(seg[2*v], seg[2*v+1]);
}
vector<pii> get(ll v, ll tl, ll tr, ll l, ll r){
if(tr < l || tl > r)
return {};
else if(l <= tl && tr <= r)
return seg[v];
else{
ll tm = (tl+tr)/2;
return merge(get(2*v, tl, tm, l, r), get(2*v+1, tm+1, tr, l, r));
}
}
ll n;
ll q;
ll solve(ll l, ll r){
vector<pii> v = get(1, 0, n-1, l, r);
ll ans = 0;
sort(v.begin(), v.end(), sfunc);
for(ll i1 = 0; i1 < v.size(); ++i1)
for(ll i2 = i1+1; i2 < v.size(); ++i2)
for(ll i3 = i2+1; i3 < v.size(); ++i3)
if(v[i2].ss-v[i1].ss <= v[i3].ss-v[i2].ss)
ans = max(ans, v[i1].ff+v[i2].ff+v[i3].ff);
return ans;
}
int main() {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin >> n;
for(ll i = 0; i < n; ++i)
cin >> a[i];
build(1, 0, n-1);
cin >> q;
while(q--){
ll l, r;
cin >> l >> r;
cout << solve(l-1, r-1) << '\n';
}
}
