/*
ROAD TO TST
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define el "\n"
#define pb push_back
#define all(v) v.begin(), v.end()
#define rep(i, x, y) for(int i = x, _y = y; i <= _y; i++)
#define rev(i, x, y) for(int i = x, _y = y; i >= _y; i--)
void file() {
#define name "C:\\Users\\hminh\\Desktop\\2026\\AIO\\test"
if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
else {
#undef name
#define name "test"
if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
}
}
const int nmax = 2e5 + 7;
int n, a[nmax], q, pref[nmax], delta[nmax], last[nmax], p[nmax];
int up[18][nmax], ans[nmax], s[nmax];
vector<int> pos;
pii Q[nmax];
int get_min(int l, int r) {
if(l > r) return 0;
int k = __lg(r - l + 1);
return min(up[k][l], up[k][r - (1 << k) + 1]);
}
int main()
{
file();
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n;
rep(i, 1, n) cin >> a[i], pref[i] = pref[i - 1] + a[i];
cin >> q;
rep(i, 1, q) cin >> Q[i].fi >> Q[i].se, last[i] = Q[i].fi;
rep(x, 1, 100) {
rep(i, 1, n) {
s[i] = s[i - 1];
if(a[i] == x) {
pos.pb(i);
s[i] += a[i];
}
up[0][i] = pref[i] - delta[i] * 2 - s[i] * 2;
}
if(pos.size() == 0) continue;
sort(all(pos));
rep(i, 1, 17) {
rep(j, 1, n - (1 << i) + 1) {
up[i][j] = min(up[i - 1][j], up[i - 1][j + (1 << (i - 1))]);
}
}
rep(i, 1, q) {
int L = lower_bound(all(pos), Q[i].fi) - pos.begin();
int R = upper_bound(all(pos), Q[i].se) - pos.begin() - 1;
int res = R + 1;
int l = L, r = R;
while(l <= r) {
int mid = (l + r) >> 1;
if(pos[mid] > last[i] && get_min(pos[mid], Q[i].se) - pref[Q[i].fi - 1] + delta[Q[i].fi - 1] * 2 + p[i] * 2 + s[pos[mid] - 1] * 2 >= 0) {
r = mid - 1;
res = mid;
}
else {
l = mid + 1;
}
}
if(res > 0) last[i] = max(last[i], pos[res - 1]);
p[i] += (res - L) * x;
ans[i] += R - res + 1;
}
int cur = 0;
rep(i, 1, n) {
if(a[i] == x) {
cur += a[i];
}
delta[i] += cur;
}
pos.clear();
}
rep(i, 1, q) cout << ans[i] << el;
return 0;
}
