#include<bits/stdc++.h>
using namespace std;
//=====================================================================================================================================
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define pii pair<int, int>
#define BIT(i, mask) ((mask >> (i)) & 1)
#define DAOBIT(i, mask) ((mask ^ (1 << i)))
#define OFFBIT(i, mask) ((mask & ~(1 << (i))))
#define ONBIT(i, mask) ((mask | (1 << (i))))
#define nmax 1000007
//=====================================================================================================================================
const int N = 1e6 + 7;
const ll mod = 1e9 + 6;
const ll MOD = 1e9 + 7;
const ll inf = 1e18;
int n, q;
int a[N];
int l, r;
//=====================================================================================================================================
void fre(){
freopen("LOIVAO.INP", "r", stdin);
freopen("LOIVAO.out", "w", stdout);
}
ll gcd(ll a, ll b){
return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b){
return (a / gcd(a, b)) * b;
}
namespace sub2{
const int N_sub2 = 5000 + 7;
int dp[N_sub2][N_sub2];
const int LG = 20 + 1;
ll st[LG + 1][N_sub2];
void sparetable(){
for(int i = 1; i <= n; ++i) st[0][i] = a[i];
for(int j = 1; j < LG; ++j){
for (int i = 1; i + (1 << j) - 1 <= n; ++i){
st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
}
}
int query(int l, int r) {
int k = __lg(r - l + 1);
return max(st[k][l], st[k][r - (1 << k) + 1]);
}
void solve(){
sparetable();
for(int i = n; i > 0; i--){
for(int j = i + 2; j <= n; j++){
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
int len = (i + j) / 2;
dp[i][j] = max(dp[i][j], a[i] + a[j] + query(i + 1, len));
}
}
while(q--){
cin >> l >> r;
cout << dp[l][r] << '\n';
}
}
}
namespace sub3{
const int LG = 20 + 1;
ll st[LG + 1][N];
void sparetable(){
for(int i = 1; i <= n; ++i) st[0][i] = a[i];
for(int j = 1; j < LG; ++j){
for (int i = 1; i + (1 << j) - 1 <= n; ++i){
st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
}
}
int query(int l, int r) {
int k = __lg(r - l + 1);
return max(st[k][l], st[k][r - (1 << k) + 1]);
}
void solve(){
sparetable();
int l, r;
cin >> l >> r;
ll res = -inf;
vector<pll> arr(n + 1);
for (int i = 1; i <= n; i++){
arr[i] = {a[i], i};
}
sort(arr.begin() + 1, arr.end(), greater<pll>());
for(int j = 1; j <= min(n, 50); j++){
for(ll i = l; i <= r; i++){
if(i != arr[j].se){
int left = min(i, arr[j].se);
int right = max(i, arr[j].se);
ll mx_left = query(max(l, 2 * left - right), left - 1);
ll mx_right = query(2 * right - left, r);
res = max(res, a[i] + arr[j].fi + max(mx_left, mx_right));
}
}
}
cout << res << '\n';
}
}
//=====================================================================================================================================
int main(){
cin.tie(0)->sync_with_stdio(0);
// fre();
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
cin >> q;
if(n <= 5000){
sub2 :: solve();
return 0;
}
if(q == 1){
sub3 :: solve();
return 0;
}
return 0;
}
