#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
int n; cin >> n;
vector<int> a(n + 1);
for(int i = 1; i <= n; i++) cin >> a[i];
int q; cin >> q;
if(n <= 100 && q <= 100){
while(q--){
int l, r; cin >> l >> r;
int ans = 0;
for(int i = l; i <= r; i++){
for(int j = i + 1; j <= r; j++){
for(int k = j + 1; k <= r; k++){
if(k - j >= j - i){
ans = max(ans, a[i] + a[j] + a[k]);
}
}
}
}
cout << ans << "\n";
}
}else if(n <= 5000){
vector<vector<int>> mx(n + 1, vector<int>(n + 1)), dp(n + 1, vector<int>(n + 1));
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 len = 2; len <= n - 1; len++){
for(int i = 1; i + len <= n; i++){
int j = i + len;
int mid = (i + j) / 2;
int L = max(1ll, i + 1), R = min(mid, j - 1);
dp[i][j] = a[i] + mx[L][R] + a[j];
dp[i][j] = max({dp[i][j], dp[i + 1][j], dp[i][j - 1]});
}
}
while(q--){
int l, r; cin >> l >> r;
cout << dp[l][r] << "\n";
}
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
}
