#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,e) for (int i = s; i <= e; ++i)
#define rrep(i,s,e) for (int i = s; i >= e; --i)
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define len(a) (int)a.size()
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
const int mx = 5e5;
int seg[4*mx+5], lazy[4*mx+5], a[mx+1], b[mx+2];
set<int> st;
void upd (int l, int r, int bl, int br, int val, int id) {
if (l==bl && r==br) {
seg[id] += val;
lazy[id] += val;
return;
}
int mid = (bl+br)/2;
if (r<=mid) upd (l, r, bl, mid, val, 2*id);
else if (l>mid) upd (l, r, mid+1, br, val, 2*id+1);
else {
upd (l, mid, bl, mid, val, 2*id);
upd (mid+1, r, mid+1, br, val, 2*id+1);
}
seg[id] = max(seg[2*id], seg[2*id+1])+lazy[id];
}
int qry (int l, int r, int bl, int br, int id) {
if (l==bl && r==br) return seg[id];
int mid = (bl+br)/2;
if (r<=mid) return lazy[id] + qry (l, r, bl, mid, 2*id);
if (l>mid) return lazy[id] + qry (l, r, mid+1, br, 2*id+1);
return lazy[id] + max( qry(l, mid, bl, mid, 2*id), qry(mid+1, r, mid+1, br, 2*id+1));
}
void adij (int i, int j) {
int x = 2*j-i;
if (x>=*st.rbegin()) return;
auto it = st.upper_bound(x);
if (it!=st.begin()) {
if (a[i]+a[j] > b[*prev(it)]) {
upd (x, *it-1, 1, mx, a[i]+a[j] - b[*prev(it)], 1);
b[x] = a[i]+a[j];
st.insert(x);
}
}
else {
upd (x, *it-1, 1, mx, a[i]+a[j], 1);
b[x] = a[i]+a[j];
st.insert(x);
}
while (a[i]+a[j] > b[*it]) {
upd (*it, *next(it)-1, 1, mx, a[i]+a[j]-b[*it], 1);
it = st.erase(it);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, q; cin >> n;
st.insert(n+1);
b[n+1] = 1e9;
vii rs[n+1];
rep (i,1,n) cin >> a[i];
cin >> q;
int ans[q+1] = {};
rep (i,1,q) {
int l, r; cin >> l >> r;
rs[l].pb({r,i});
}
stack<int> js;
rrep (i,n,1) {
upd (i, i, 1, mx, a[i], 1);
while ( len(js) && a[js.top()] < a[i]) {
adij(i, js.top());
js.pop();
}
if (len(js)) adij(i, js.top());
js.push(i);
for (ii ri : rs[i]) ans[ri.se] = qry (i+2, ri.fi, 1, mx, 1);
}
rep (i,1,q) cout << ans[i] << "\n";
return 0;
}
