#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 = 5e5+5 , maxn = 3e5 + 5;
const int MOD = 1e9+7;
struct tree{
int cnt , l , r;
};
int n , q , a[N] , mx[N][21] , lg[N];
tree t[4 * N];
tree merge(tree a , tree b){
tree res;
if (a.cnt != b.cnt){
if (a.cnt < b.cnt) res = b;
else res = a;
}
else {
res.cnt = a.cnt;
res.l = min(a.l , b.l);
res.r = max(a.r , b.r);
}
return res;
}
void build(int v , int tl , int tr){
if (tl == tr){
t[v] = {a[tl] , tl , tl};
return;
}
int tm = (tl + tr) / 2;
build(v * 2 , tl , tm) , build(v * 2 + 1 , tm + 1, tr);
t[v] = merge(t[v * 2] , t[v * 2 + 1]);
}
tree get(int v , int tl , int tr , int l , int r){
if (tr < l or r < tl) return {0 , 0 , 0};
if (l <= tl and tr <= r) return t[v];
int tm = (tl + tr) / 2;
return merge(get(v * 2 , tl , tm , l , r) , get(v * 2 + 1 , tm + 1, tr , l , r));
}
void update(int v , int tl , int tr , int i , int x){
if (tl == tr){
t[v].cnt = x;
return;
}
int tm = (tl + tr) / 2;
if (i <= tm) update(v * 2 , tl , tm , i , x);
else update(v * 2 + 1 , tm + 1 , tr , i , x);
t[v] = merge(t[v * 2] , t[v * 2 + 1]);
}
int gmx(int l , int r){
int j = lg[r - l + 1];
int sum = max(mx[l][j] , mx[r - (1<<j) + 1][j]);
return sum;
}
void arkanefury228(){
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
mx[i][0] = a[i];
}
for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
for (int j = 1; j < 20; j++){
for (int i = 1; i <= n - (1 << j) + 1; i++){
mx[i][j] = max(mx[i][j - 1] , mx[i + (1 << (j - 1))][j - 1]);
}
}
cin >> q;
build(1 , 1 , n);
while(q--){
int l , r , ans = 0;
bool t = 0;
vector<int> p;
cin >> l >> r;
while(p.size() != r - l + 1 and p.size() < 200){
t = 1 - t;
auto gt = get(1 , 1 , n , l , r);
int pos = 0;
if (t == 0) pos = gt.l;
else pos = gt.r;
p.pb(pos);
update(1 , 1 , n , pos , 0);
}
sort(all(p));
for (int i = 0; i < p.size(); i++){
for (int j = i + 1; j < p.size(); j++){
if (p[j] - p[i] + 1 <= 2) continue;
ans = max(ans , a[p[j]] + a[p[i]] + gmx(p[i] + 1 , (p[i] + p[j]) / 2));
}
}
for (int i = 0; i < p.size(); i++){
for (int j = i + 1; j < p.size(); j++){
if (p[j] + (p[j] - p[i]) > r) continue;
ans = max(ans , a[p[j]] + a[p[i]] + gmx(p[j] + (p[j] - p[i]) , r));
}
}
for (int i = 0; i < p.size(); i++){
if (p[i] == l) continue;
for (int j = i + 1; j < p.size(); j++){
ans = max(ans , a[p[i]] + a[p[j]] + gmx(max(l , p[i] - (p[j] - p[i])) , p[i] - 1));
}
}
for (auto i : p){
update(1 , 1 , n , i , a[i]);
}
cout << ans << ent;
}
}
signed main(){
PRaim_bek_abi
int t=1;
//cin>>t;
for (int respagold = 1; respagold <= t; respagold++) arkanefury228();
}
