#include <bits/stdc++.h>
using namespace std;
template <typename T> using vc = vector<T>;
struct UnionFind {
int n, n_comp;
vc<int> dat; // par or (-size)
UnionFind(int n = 0) { build(n); }
void build(int m) {
n = m, n_comp = m;
dat.assign(n, -1);
}
void reset() { build(n); }
int operator[](int x) {
while (dat[x] >= 0) {
int pp = dat[dat[x]];
if (pp < 0) {
return dat[x];
}
x = dat[x] = pp;
}
return x;
}
bool merge(int x, int y) {
x = (*this)[x], y = (*this)[y];
if (x == y)
return false;
if (-dat[x] < -dat[y])
swap(x, y);
dat[x] += dat[y], dat[y] = x, n_comp--;
return true;
}
};
struct QUERY {
int id, L, now;
QUERY(int id, int L, int now) : id(id), L(L), now(now) {}
};
const int LIM = 100;
void solve() {
cin.tie(0);
ios_base::sync_with_stdio(0);
int N;
cin >> N;
vc<int> A(N);
for (int i = 0; i < N; ++i)
cin >> A[i];
int Q;
cin >> Q;
vc<int> ANS(Q);
vc<vc<QUERY>> query(N + 1);
for (int q = 0; q < Q; ++q) {
int L, R;
cin >> L >> R;
--L;
query[R].emplace_back(QUERY(q, L, 0));
}
UnionFind uf(N + 1);
vc<int> left(N + 1);
vc<int> val(N + 1);
vc<int> sm_0(N + 1), sm_1(N + 1);
for (int i = 0; i < N; ++i)
sm_1[i + 1] = sm_1[i] + A[i];
vc<int> cnt(N + 1);
for (int x = 1; x <= LIM; ++x) {
swap(sm_0, sm_1);
vc<int> I;
for (int i = 0; i < N; ++i) {
sm_1[i + 1] = sm_1[i] + (A[i] < x + 1 ? -A[i] : A[i]),
cnt[i + 1] = cnt[i] + (A[i] == x);
if (A[i] == x)
I.emplace_back(i);
}
// sm[x+1] の区間最小値を管理する
uf.reset();
val[0] = 0;
for (int R = 1; R <= N; ++R) {
val[R] = sm_1[R], left[R] = R;
while (1) {
int p = left[uf[R]] - 1;
if (p == -1 || val[p] < val[R])
break;
int l = left[uf[p]];
uf.merge(R, p);
int k = uf[R];
left[k] = l, val[k] = val[R];
}
for (auto &X : query[R]) {
if (X.L == R)
continue;
int L = X.L;
int nx = cnt[R] - cnt[L];
// x を負で使ったときの
int mi = X.now + val[uf[L]] - sm_1[L];
int need = (-mi + 2 * x - 1) / (2 * x);
need = max(need, 0);
ANS[X.id] += nx - need;
if (need > 0) {
int idx = I[cnt[L] + need - 1];
X.now += sm_0[idx + 1] - sm_0[L];
X.L = idx + 1;
}
}
}
}
for (auto &x : ANS) {
cout << x << "\n";
}
}
signed main() {
solve();
return 0;
}
