#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, q, x, y;
cin >> n;
int a[n], smx[n+1][n+1];
for(int i = 0; i < n; i++) cin >> a[i];
for(int j = 0; j < n; j++) {
smx[j][j] = a[j];
for(int i = j-1; i >= 0; i--) {
smx[i][j] = max(smx[i+1][j], a[i]);
}
for(int i = j+1; i <= n; i++) smx[i][j] = 0;
}
cin >> q;
while(q--) {
cin >> x >> y;
x--; y--;
int ans = 0;
for(int i = x; i <= y; i++) {
for(int j = i+1; j < y; j++) {
ans = max(ans, a[i]+a[j]+smx[min(2*j-i, n)][y]);
}
}
cout << ans << '\n';
}
}
