#include <bits/stdc++.h>
// #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
typedef pair<long double, ll> pp;
#define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ss second
#define ff first
void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353, maxn = 5e3 + 5, lg = 19, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}
ll a[maxn];
int n, q;
void slv2(){
vector<vector<ll>> mx(n, vector<ll>(n, -inf));
rep(i,0,n){
mx[i][i] = a[i];
rep(j,i+1,n) mx[i][j] = max(mx[i][j-1], a[j]);
}
vector<vector<ll>> ans(n, vector<ll>(n, -inf));
rep(l,3,n+1){
rep(i,0,n-l+1){
int j = i + l - 1;
ans[i][j] = max({ans[i+1][j], ans[i][j-1], a[i] + a[j] + mx[i+1][(i+j)>>1]});
}
}
while(q--){
int l, r; cin >> l >> r;
cout << ans[--l][--r] << '\n';
}
}
void slv3(){
int l, r; cin >> l >> r; l--, r--, n = r - l + 1;
vector<int> b(a + l, a + r + 1);
vector<vector<int>> rmq(n, vector<int>(lg));
vector<int> lgg(n + 1);
rep(i,2,n+1) lgg[i] = lgg[i>>1] + 1;
rep(i,0,n) rmq[i][0] = b[i];
rep(j,1,lg) rep(i,0,n-(1<<j)+1) rmq[i][j] = max(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]);
auto get_max = [&](int l, int r){
if(r < 0 || l > r) return -1;
l = max(l, 0), r = min(n-1, r);
int k = lgg[r-l+1];
return max(rmq[l][k], rmq[r-(1<<k)+1][k]);
};
auto clc = [&](int i){
ll res = -inf;
// right
rep(j,0,i) res = max(res, 1ll*b[i] + b[j] + get_max(j-(i-j),j-1));
// center
rep(j,0,i) res = max(res, 1ll*b[i] + b[j] + get_max(i+(i-j),n-1));
// left
rep(j,i+1,n) res = max(res, 1ll*b[i] + b[j] + get_max(j+(j-i),n-1));
return res;
};
vector<int> c(n); iota(all(c), 0), sort(all(c), [&](int i, int j){ return b[i] > b[j]; });
ll ans = 0; int g = min(lgg[n]+3, n);
rep(i,0,g){
ans = max(ans, clc(c[i]));
}
cout << ans << '\n';
}
int main(){
cin.tie(0) -> sync_with_stdio(0);
cin >> n;
rep(i,0,n) cin >> a[i];
cin >> q;
if(q>1) slv2();
else slv3();
return 0;
}
