/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 2e6+100, M = 1e5+10, K = 22, MX = 30;
struct Fenwick{
int n;
vector<int> t;
Fenwick(int _n){
n = _n;
t.resize(n+1, 0);
}
void add(int v){
while(v <= n){
t[v]++;
v += (v&-v);
}
}
int get(int v){
int res = 0;
while(v > 0){
res += t[v];
v -= (v&-v);
}
return res;
}
};
int n, a[N], q, L[N], R[N], rmq[N][K], go[N], T[N], C[N], ans[N], COMB[N];
vector<pii> Q[N], to[N];
int comb(int x, int y){
return max(x,y);
}
int get(int l, int r){
int k = int(log2(r-l+1));
return max(rmq[l][k], rmq[r-(1<<k)+1][k]);
}
void build(int l, int r, int k){
C[k] = 0;
if(l == r){
T[k] = a[l];
COMB[k] = a[l];
return;
}
int m = l+r>>1;
build(l, m, k<<1);
build(m+1, r, k<<1|1);
COMB[k] = comb(COMB[k<<1], COMB[k<<1|1]);
T[k] = comb(T[k<<1], T[k<<1|1]);
}
int get_max(int l, int r, int ql, int qr, int k){
if(ql > r || l > qr) return 0;
if(ql <= l && r <= qr) return max(COMB[k], T[k]+C[k]);
C[k<<1] = max(C[k<<1], C[k]);
C[k<<1|1] = max(C[k<<1|1], C[k]);
int m = l+r>>1;
auto v = comb(get_max(l, m, ql, qr, k<<1), get_max(m+1, r, ql, qr, k<<1|1));
return v;
}
void upd(int l, int r, int ql, int qr, int k, int val){
if(ql > r || l > qr) return;
if(ql <= l && r <= qr){
C[k] = max(val, C[k]);
COMB[k] = max(COMB[k], C[k] + T[k]);
// cout << COMB[k] << '\n';
return;
}
C[k<<1] = max(C[k<<1], C[k]);
C[k<<1|1] = max(C[k<<1|1], C[k]);
int m = l+r>>1;
upd(l, m, ql, qr, k<<1, val);
upd(m+1, r, ql, qr, k<<1|1, val);
COMB[k] = max({COMB[k<<1], COMB[k<<1|1], C[k] + T[k]});
// cout << COMB[k] << ' '<< l << ' ' << r << '\n';
}
void solve(){
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> a[i];
rmq[i][0] = a[i];
}
deque<int> A;
for(int i = 1; i <= n; ++i){
while(A.size() && a[A.back()] < a[i]) A.pop_back();
L[i] = A.size() == 0 ? - 1 : A.back();
A.pb(i);
if(L[i] > -1){
to[L[i]].pb({a[i] + a[L[i]], i + i - L[i]});
}
}
A.clear();
for(int i = n; i >= 1; --i){
while(A.size() && a[A.back()] < a[i]) A.pop_back();
R[i] = A.size() == 0 ? - 1 : A.back();
A.pb(i);
if(R[i] > -1)
to[i].pb({a[i] + a[R[i]], R[i] + R[i] - i});
}
for(int j = 1; j < K; ++j){
for(int i = 1; i + (1<<j) <= n + 1; ++i){
rmq[i][j] = max(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]);
}
}
build(1, n, 1);
cin >> q;
for(int i = 1; i <= q; ++i){
int l, r; cin >> l >> r;
Q[l].pb({r, i});
}
for(int i = n; i >= 1; --i){
for(auto p: to[i]){
if(p.ss <= n){
// cout << p.ff << ' ' << p.ss << ' ' << i << '\n';
upd(1, n, p.ss, n, 1, p.ff);
}
}
for(auto p: Q[i]){
ans[p.ss] = get_max(1, n, i, p.ff, 1);
}
}
for(int i = 1; i <= q; ++i){
cout << ans[i] << '\n';
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
en;
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
