#include <bits/stdc++.h>;
#define int long long
using namespace std;
using pii = pair<int, int>;
const int li = 5e5 + 10;
void print() { cerr << '\n'; }
template<typename T, typename... Args>
void print(T first, Args... rest) {
cerr << first << ' ';
print(rest...);
}
int n, a[li], q;
pii Q[li];
void solve1() {
for (int i=1; i<=q; i++) {
int l = Q[i].first, r = Q[i].second;
int ans = 0;
for (int z=l+2; z<=r; z++) {
for (int x=l; x<=z-2; x++) {
for (int y=x+1; y - x <= z - y; y++) {
ans = max(ans, a[x] + a[y] + a[z]);
}
}
}
cout << ans << '\n';
}
}
int seg[li * 4];
int left(int id) { return (id << 1); }
int right(int id) { return (id << 1 | 1); }
void build(int id = 1, int l = 1, int r = n) {
if (l == r) { seg[id] = a[l]; return; }
int mid = (l + r) >> 1;
build(left(id), l, mid);
build(right(id), mid + 1, r);
seg[id] = max(seg[left(id)], seg[right(id)]);
}
int get(int lo, int hi, int id = 1, int l = 1, int r = n) {
if (r < lo || l > hi) return 0;
if (l >= lo && r <= hi) return seg[id];
int mid = (l + r) >> 1;
return max(get(lo, hi, left(id), l, mid), get(lo, hi, right(id), mid + 1, r));
}
int pre[5001][5001];
void solve2() {
build();
for (int x=1; x<=n-2; x++) {
for (int z = x + 2; z<=n; z++) {
pre[x][z] = get(x + 1, ((z + x) >> 1)) + a[x] + a[z];
}
}
for (int i=1; i<=q; i++) {
int l = Q[i].first, r = Q[i].second;
int ans = 0;
for (int z=l+2; z<=r; z++) {
for (int x=l; x<=z-2; x++) {
ans = max(ans, pre[x][z]);
}
}
cout << ans << '\n';
}
}
signed main(){
cin >> n;
for (int i=1; i<=n; i++) cin >> a[i];
cin >> q;
for (int i=1; i<=q; i++) cin >> Q[i].first >> Q[i].second;
solve2();
return 0;
}
