#include <bits/stdc++.h>
#define int long long
#define ent '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define PRaim_bek_abi ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
const int N = 5e3+5 , maxn = 3e5 + 5;
const int MOD = 1e9+7;
int n , q , a[N] , mx[N][N] , ans[N][N] , suf[N][N];
void arkanefury228(){
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
for (int l = 1; l <= n; l++){
int m = a[l];
for (int r = l; r <= n; r++){
m = max(m , a[r]);
mx[l][r] = m;
}
}
for (int r = 1; r <= n; r++){
for (int l = 1; l <= r; l++){
if (r - l + 1 <= 2) break;
int sum = a[r] + a[l] + mx[l + 1][(r + l) / 2];
ans[l][r] = max(ans[l][r - 1] , sum);
}
}
for (int i = 1; i <= n; i++){
for (int j = i; j >= 1; j--){
suf[j][i] = max(ans[j][i] , suf[j + 1][i]);
}
}
cin >> q;
while(q--){
int l , r;
cin >> l >> r;
cout << suf[l][r] << ent;
}
}
signed main(){
PRaim_bek_abi
int t=1;
//cin>>t;
for (int respagold = 1; respagold <= t; respagold++) arkanefury228();
}
