#include <bits/stdc++.h>
using namespace std;
#define int long long
using ii = pair<int, int>;
const int N = 5e5 + 5;
const long long INF = 1e17;
int n, q, a[N];
ii query[N];
namespace sub12{
const int N = 5e3 + 5;
int mx[N][N], dp[N][N];
void solve(){
for(int i = 1; i <= n; i++)
for(int j = i; j <= n; j++) mx[i][j] = max(mx[i][j - 1], a[j]);
for(int i = n; i >= 1; i--)
for(int j = i + 2; j <= n; j++){
dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
dp[i][j] = max(dp[i][j], a[i] + a[j] + mx[i + 1][(i + j)/2]);
}
for(int i = 1; i <= q; i++) cout << dp[query[i].first][query[i].second] << "\n";
}
}
namespace sub3{
const int N = 2e5 + 5;
int mx[N][20], lg[N], dp[N];
int get(int l, int r){
if(l > r) return -INF;
int k = lg[r - l + 1];
return max(mx[l][k], mx[r - (1 << k) + 1][k]);
}
void dnc(int l, int r, int optl, int optr){
if(l > r) return;
int mid = l + r >> 1, opt = -1;
for(int i = optl; i <= min(mid - 1, optr); i++){
int value = a[mid] + a[i] + get(max(1LL, 2*i - mid), i - 1);
if(value > dp[mid]){
dp[mid] = value;
opt = i;
}
}
dnc(l, mid - 1, optl, opt);
dnc(mid + 1, r, opt, optr);
}
void solve(){
for(int i = 1; i <= n; i++) mx[i][0] = a[i];
for(int j = 1; j <= 17; j++)
for(int i = 1; i + (1 << j) - 1 <= n; i++)
mx[i][j] = max(mx[i][j - 1], mx[i + (1 << j - 1)][j - 1]);
for(int i = 2; i <= n; i++) lg[i] = lg[i/2] + 1;
dnc(1, n, 1, n);
cout << *max_element(dp + 3, dp + n + 1) << "\n";
}
}
int32_t main(){
cin.tie(0)->sync_with_stdio(0);
// #define task "test"
// if(fopen(task ".inp", "r")){
// freopen(task ".inp", "r", stdin);
// freopen(task ".out", "w", stdout);
// }
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
cin >> q;
for(int i = 1; i <= q; i++) cin >> query[i].first >> query[i].second;
if(n <= 5000) sub12::solve();
else if(q == 1 && query[1] == make_pair(1LL, n)) sub3::solve();
else sub12::solve();
return 0;
}
