#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N, Q, a, b; cin >> N;
vector<int> A, precomp, preva, crnt, qA, qB;
vector<vector<int>> idxs(101, vector<int>()), prefs(101, vector<int>(N + 1, 0)), sparse(18, vector<int>());
for (int i = 0; i < N; i++) {
cin >> a;
A.push_back(a);
idxs[a].push_back(i);
prefs[0][i + 1] = prefs[0][i] + a;
for (int j = 1; j <= 100; j++) prefs[j][i + 1] = prefs[j][i] + (a <= j ? -a : a);
}
cin >> Q;
precomp.resize(Q, 0);
crnt.resize(Q, 0);
for (int i = 0; i < Q; i++) {
cin >> a >> b; a--, b--;
qA.push_back(a);
qB.push_back(b);
preva.push_back(a);
}
sparse[0].resize(N + 1, 0);
for (int i = 1; i < 18; i++) sparse[i].resize(max(0LL, (int)sparse[i - 1].size() - (1LL << (i - 1))), 0);
for (int i = 1; i <= 100; i++) {
for (int j = 0; j <= N; j++) sparse[0][j] = prefs[i][j];
for (int j = 1; j < 18; j++)
for (int k = 0; k < sparse[j].size(); k++)
sparse[j][k] = min(sparse[j - 1][k], sparse[j - 1][k + (1LL << (j - 1))]);
for (int j = 0; j < Q; j++) {
auto iter1 = lower_bound(idxs[i].begin(), idxs[i].end(), qA[j]);
auto iter2 = upper_bound(idxs[i].begin(), idxs[i].end(), qB[j]);
if (iter1 == iter2) continue;
int log2v = log2(qB[j] - qA[j] + 1);
int minpref = min(sparse[log2v][qA[j] + 1], sparse[log2v][qB[j] + 2 - (1LL << log2v)]) - prefs[i][qA[j]] + precomp[j];
minpref = max(0LL, -minpref);
int numflip = (minpref + 2 * i - 1) / (2 * i);
crnt[j] += iter2 - iter1 - numflip;
preva[j] = qA[j];
if (iter2 - iter1 > numflip - 1 && numflip) qA[j] = *(iter1 + numflip - 1) + 1;
precomp[j] += prefs[i - 1][qA[j]] - prefs[i - 1][preva[j]];
}
}
for (int i = 0; i < Q; i++) cout << crnt[i] << '\n';
}
