#include<bits/stdc++.h>
#define int long long
#define ii pair<int, int>
using namespace std;
const int N = 5e5 + 5;
int n, q;
int a[N];
ii query[N];
namespace sub1 {
void solve() {
for(int i = 1; i <= q; ++i) {
auto [l, r] = query[i];
int res = 0;
for(int x = l; x <= r; ++x)
for(int y = x + 1; y <= r; ++y)
for(int z = y + (y - x); z <= r; ++z) res = max(res, a[x] + a[y] + a[z]);
cout << res << '\n';
}
}
}
namespace sub2 {
int f[5'005][5'005], mx[5'005][5'005];
void solve() {
for(int i = 1; i <= n; ++i) {
mx[i][i] = a[i];
for(int j = i + 1; j <= n; ++j) mx[i][j] = max(mx[i][j - 1], a[j]);
}
for(int i = 1; i <= n; ++i)
for(int j = i + 2; j <= n; ++j)
f[i][j] = a[i] + a[j] + mx[i + 1][(i + j >> 1)];
for(int i = n; i; --i)
for(int j = i + 3; j <= n; ++j) {
f[i][j] = max({f[i][j], f[i + 1][j], f[i][j - 1]});
if(j - i - 1 >= 3) f[i][j] = max(f[i][j], f[i + 1][j - 1]);
}
for(int i = 1; i <= q; ++i) cout << f[query[i].first][query[i].second] << '\n';
}
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for(int i = 1; i <= n; ++i) cin >> a[i];
cin >> q;
for(int i = 1; i <= q; ++i) cin >> query[i].first >> query[i].second;
if(n <= 100 && q <= 100) sub1 :: solve();
else if(n <= 5'000) sub2 :: solve();
}
