#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
constexpr ll inf = 1ll << 62ll;
mt19937 mt(time(0));
ll _ = 0;
struct segtree {
struct node {
ll mx = -inf, bord = -inf, lz_mx = -inf;
};
ll nt;
vector<node> tree;
segtree(vector<ll> &a) {
nt = 1;
while (nt < sz(a)) nt *= 2;
tree = vector<node>(2*nt);
for (ll i = 0; i < sz(a); i++) {
tree[nt+i].mx = a[i] - inf;
}
for (ll i = nt-1; i > 0; i--) {
recalc(i);
}
}
void recalc(ll k) {
assert(k < nt);
tree[k].mx = max(tree[2*k].mx, tree[2*k+1].mx);
ll dl = tree[k].mx - tree[2*k].mx;
ll dr = tree[k].mx - tree[2*k+1].mx;
tree[k].bord = min(tree[2*k].bord + dl, tree[2*k+1].bord + dr);
}
void prop(ll k) {
if (k < nt) {
tree[2*k].lz_mx = max(tree[2*k].lz_mx, tree[k].lz_mx);
tree[2*k+1].lz_mx = max(tree[2*k+1].lz_mx, tree[k].lz_mx);
}
if (tree[k].lz_mx <= tree[k].bord) return;
ll diff = tree[k].lz_mx - tree[k].bord;
tree[k].mx += diff;
tree[k].bord += diff;
}
void range_update_max(ll l, ll r, ll v) { return range_update_max(1, 0, nt-1, l, r, v); }
void range_update_max(ll k, ll tl, ll tr, ll l, ll r, ll v) {
prop(k);
if (r < tl || l > tr) return;
if (l <= tl && r >= tr) {
tree[k].lz_mx = max(tree[k].lz_mx, v);
prop(k);
return;
}
ll mid = tl + (tr - tl) / 2;
range_update_max(2*k, tl, mid, l, r, v);
range_update_max(2*k+1, mid+1, tr, l, r, v);
recalc(k);
}
ll range_query_max(ll l, ll r) { return range_query_max(1, 0, nt-1, l, r); }
ll range_query_max(ll k, ll tl, ll tr, ll l, ll r) {
prop(k);
if (r < tl || l > tr) return -inf;
if (l <= tl && r >= tl) return tree[k].mx;
ll mid = tl + (tr - tl) / 2;
return max(range_query_max(2*k, tl, mid, l, r), range_query_max(2*k+1, mid+1, tr, l, r));
}
};
void solve() {
ll n; cin >> n;
vector<ll> a(n);
for (auto &e : a) cin >> e;
ll q; cin >> q;
while (q--) {
ll l, r; cin >> l >> r; l--; r--;
ll res = 0;
for (ll i = l; i <= r; i++) {
for (ll j = i+1; j <= r; j++) {
for (ll k = i + (j - i) * 2; k <= r; k++) {
res = max(res, a[i] + a[j] + a[k]);
}
}
}
cout << res << '\n';
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
solve();
}
