#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
#define ff first
#define ss second
#define pi pair<int, int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vll vector<long long>
#define vpi vector<pair<int,int>>
#define vpll vector<pair<long long, long long>>
#define pb push_back
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
#define mp make_pair
pi operator+(pi a, pi b) { return mp(a.ff+b.ff, a.ss+b.ss); }
pi operator-(pi a, pi b) { return mp(a.ff-b.ff, a.ss-b.ss); }
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
char buf[200'000], *bufp = buf;
#pragma GCC optimize("O3,unroll-loops")
#ifdef _WIN32
#define getchar_unlocked getchar
#define putchar_unlocked putchar
#endif
inline int readint() {
char c = getchar_unlocked();
while((c < '0' || c > '9') && c != '-') c = getchar_unlocked();
bool neg = false;
if(c == '-') neg = true, c = getchar_unlocked();
int res = 0;
while(c >= '0' && c <= '9') res = res * 10 + c - '0', c = getchar_unlocked();
return neg? -res : res;
}
char _buf[40];
inline void printint(int n) {
if(n == 0) putchar_unlocked('0');
if(n < 0) putchar_unlocked('-'), n = -n;
int i = 0;
for(; n > 0; n /= 10) _buf[i++] = n % 10 + '0';
while(i--) putchar_unlocked(_buf[i]);
putchar_unlocked('\n');
}
struct DataStructure {
int n, K;
vector<vector<int>> st;
vector<int> lg;
void build(const vector<int>& a) {
n = a.size();
K = 32 - __builtin_clz(n);
st.assign(K, vector<int>(n));
lg.assign(n + 1, 0);
// logi
for (int i = 2; i <= n; i++)
lg[i] = lg[i / 2] + 1;
// poziom 0
for (int i = 0; i < n; i++)
st[0][i] = a[i];
// budowa
for (int k = 1; k < K; k++) {
for (int i = 0; i + (1 << k) <= n; i++) {
st[k][i] = min(
st[k - 1][i],
st[k - 1][i + (1 << (k - 1))]
);
}
}
}
int query(int l, int r) {
int k = lg[r - l + 1];
return min(
st[k][l],
st[k][r - (1 << k) + 1]
);
}
void destroy() {
for (auto &v : st) {
v.clear();
v.shrink_to_fit();
}
st.clear();
st.shrink_to_fit();
lg.clear();
lg.shrink_to_fit();
n = K = 0;
}
};
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n=readint();
vector<int> a(n+1);
for(int i=1; i<=n; ++i) a[i] = readint();
int A = 100;
vector<vector<int>> prefix(A+1, vector<int>(n+1, 0));
for(int l=0; l<=A; ++l) {
for(int i=1; i<=n; ++i) {
prefix[l][i] = prefix[l][i-1] + (a[i] <= l ? -a[i] : a[i]);
}
}
vector<DataStructure> ds(A+1);
for(int i=0; i<=0; ++i) ds[i].build(prefix[i]);
vector<vector<int>> occ(A+1);
for(int i=1; i<=n; ++i) occ[a[i]].push_back(i);
int q=readint();
vector<int> res(q), pref_sum(q), l(q), r(q);
vector<pi> border(q);
for(int tc=0; tc<q; ++tc) {
l[tc]=readint();
r[tc]=readint();
border[tc] = {l[tc],0};
pref_sum[tc] = 0;
}
for(int x=1; x<=A; ++x) {
ds[x].build(prefix[x]);
for(int tc=0; tc<q; ++tc) {
auto before_border = [&](int X) {
int sum = prefix[border[tc].second][X-1] - prefix[border[tc].second][border[tc].first-1] + pref_sum[tc];
return sum;
};
int L = lower_bound(occ[x].begin(), occ[x].end(), l[tc]) - occ[x].begin();
int R = upper_bound(occ[x].begin(), occ[x].end(), r[tc]) - occ[x].begin() - 1;
if(L > R) continue;
int lo = L;
int hi = R;
if(before_border(occ[x][R]) + ds[x].query(occ[x][R], r[tc]) - prefix[x][occ[x][R]-1] < 0) continue;
while(lo < hi) {
int mid = (lo+hi)/2;
int p = occ[x][mid];
if(before_border(p) + ds[x].query(p, r[tc]) - prefix[x][p-1] < 0) lo = mid+1;
else hi = mid;
}
res[tc] += R-lo+1;
int p = occ[x][lo];
pref_sum[tc] += prefix[border[tc].second][p-1] - prefix[border[tc].second][border[tc].first - 1];
border[tc] = {p,x};
}
ds[x].destroy();
}
for(int i=0; i<q; ++i) printint(res[i]);
return 0;
}
