#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int MAXN = 500000 + 5;
// dữ liệu
int n, q;
ll A[MAXN];
vector<int> g[MAXN]; // g[i] chứa các j sao cho (i, j) là candidate (lưu khi build)
vector<vector<pair<int,int>>> queries; // queries[L] = vector of (R, idx)
ll ans[MAXN];
struct Seg {
int N;
vector<ll> seg, mx, lz;
Seg(int n=0){ init(n); }
void init(int n){
N = 1;
while(N < n) N <<= 1;
seg.assign(2*N, (ll)LLONG_MIN/4);
mx.assign(2*N, (ll)LLONG_MIN/4);
lz.assign(2*N, 0);
}
// build leaves with A[1..n]
void build(int n){
for(int i=0;i<n;i++){
mx[N+i] = A[i+1];
seg[N+i] = A[i+1]; // initial best_base = 0 => seg = 0 + A[i]
}
for(int i=n;i<N;i++){
mx[N+i] = (ll)LLONG_MIN/4;
seg[N+i] = (ll)LLONG_MIN/4;
}
for(int v=N-1; v>=1; --v){
mx[v] = max(mx[v<<1], mx[v<<1|1]);
seg[v] = max(seg[v<<1], seg[v<<1|1]);
}
}
inline void apply_node(int v, ll base){
// setting best_base = max(best_base, base) implies
// seg[v] = max(seg[v], base + mx[v])
if(base == 0) return;
seg[v] = max(seg[v], base + mx[v]);
lz[v] = max(lz[v], base);
}
inline void push(int v){
if(v>=N) return;
if(lz[v]){
apply_node(v<<1, lz[v]);
apply_node(v<<1|1, lz[v]);
lz[v] = 0;
}
}
// update range [L, R] (1-indexed inclusive) with best_base = max(best_base, val)
void upd_range(int L, int R, ll val){ if(L>R) return; upd_range_impl(L, R, val, 1, 1, N); }
void upd_range_impl(int L, int R, ll val, int v, int l, int r){
if(L > r || R < l) return;
if(L <= l && r <= R){
apply_node(v, val);
return;
}
push(v);
int m = (l + r) >> 1;
upd_range_impl(L, R, val, v<<1, l, m);
upd_range_impl(L, R, val, v<<1|1, m+1, r);
seg[v] = max(seg[v<<1], seg[v<<1|1]);
}
// query max seg over [L, R] inclusive
ll query(int L, int R){ if(L>R) return (ll)LLONG_MIN/4; return query_impl(L, R, 1, 1, N); }
ll query_impl(int L, int R, int v, int l, int r){
if(L > r || R < l) return (ll)LLONG_MIN/4;
if(L <= l && r <= R) return seg[v];
push(v);
int m = (l + r) >> 1;
return max(query_impl(L, R, v<<1, l, m), query_impl(L, R, v<<1|1, m+1, r));
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int i=1;i<=n;i++) cin >> A[i];
// build candidate edges g using a monotonic stack approach (as in official solutions)
// sentinel 0 with very large value
A[0] = (ll)1e18;
vector<int> st;
st.push_back(0);
for(int i=1;i<=n;i++){
while(!st.empty() && A[st.back()] <= A[i]){
g[st.back()].push_back(i);
st.pop_back();
}
g[st.back()].push_back(i);
st.push_back(i);
}
cin >> q;
queries.assign(n+2, {});
for(int i=1;i<=q;i++){
int L,R; cin >> L >> R;
// note: query will be handled when sweeping i = L
queries[L].push_back({R, i});
}
// segment tree init & build with A values
Seg seg;
seg.init(n);
seg.build(n);
// sweep i from n down to 1:
// when at i, for each x in g[i], we add candidate (i, x) which affects all c = k with k >= 2*x - i
for(int i=n;i>=1;i--){
for(int x : g[i]){
// candidate pair (i, x). threshold k0 = 2*x - i
long long k0 = 2LL * x - i;
if(k0 <= n){
// update range [k0..n] best_base = max(best_base, A[i]+A[x])
seg.upd_range((int)k0, n, A[i] + A[x]);
}
}
// answer queries with L == i:
for(auto &pr : queries[i]){
int R = pr.first;
int idx = pr.second;
// valid c must satisfy i < b < c <= R and b-a <= c-b -> minimal c is i+2, so c range [i+2..R]
if(i + 2 <= R){
ans[idx] = seg.query(i+2, R);
} else {
ans[idx] = LLONG_MIN/4; // shouldn't happen because problems ensure L+2 <= R
}
}
}
for(int i=1;i<=q;i++){
cout << ans[i] << '\n';
}
return 0;
}
