#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define Mp make_pair
#define sep ' '
#define endl '\n'
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define kill(res) cout << res << '\n', exit(0);
#define set_dec(x) cout << fixed << setprecision(x);
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);
#define lid (id*2)
#define rid (id*2+1)
#define mid ((l+r)/2)
const ll N = 5e5 + 50;
const ll Mod = 1e18;
ll n, q, arr[N], res[N];
vector<int> sta;
vector<pii> qu[N];
pll seg[N*4]; ll lz[N*4];
pll merg(pll l, pll r){
return {max(l.F, r.F), max(l.S, r.S)};
}
void build(int l = 1, int r = n+1, int id = 1){
if(l+1 == r){
seg[id].F = seg[id].S = arr[l];
return;
}
build(l, mid, lid);
build(mid, r, rid);
seg[id] = merg(seg[lid], seg[rid]);
}
void quex(int id, ll x){
seg[id].F = max(seg[id].F, seg[id].S + x);
lz[id] = max(lz[id], x);
}
void relax(int id){
quex(lid, lz[id]);
quex(rid, lz[id]);
}
void upd(int ql, int qr, ll x, int l = 1, int r = n+1, int id = 1){
if(qr <= l || r <= ql) return;
if(ql <= l && r <= qr){
quex(id, x); return;
}
relax(id);
upd(ql, qr, x, l, mid, lid);
upd(ql, qr, x, mid, r, rid);
seg[id] = merg(seg[lid], seg[rid]);
}
pll get(int ql, int qr, int l = 1, int r = n+1, int id = 1){
if(qr <= l || r <= ql) return {0, 0};
if(ql <= l && r <= qr) return seg[id];
relax(id);
return max(get(ql, qr, l, mid, lid), get(ql, qr, mid, r, rid));
}
int main(){
fast_io;
cin >> n;
for(int i = 1; i <= n; i++) cin >> arr[i];
cin >> q;
for(int i = 1; i <= q; i++){
int l, r;
cin >> l >> r;
qu[l].pb({r, i});
}
build();
sta.pb(n);
for(int i = n-1; i >= 1; i--){
while(!sta.empty()){
int lst = sta.back(); sta.pop_back();
upd(lst + lst - i, n+1, arr[i] + arr[lst]);
if(arr[lst] >= arr[i]){
sta.pb(lst); break;
}
}
sta.pb(i);
for(auto [j, id]: qu[i]) res[id] = get(i, j+1).F;
}
for(int i = 1; i <= q; i++) cout << res[i] << endl;
}
