#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) (ll)(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>;
struct DataStructure {
using T = int;
static constexpr uint32_t B = 16;
uint32_t n = 0, m = 0, size = 0;
int h = 0;
vector<vector<T>> st;
vector<T> val, pre, suf;
static constexpr T id() {
return numeric_limits<T>::max();
}
static constexpr T op(const T& a, const T& b) {
return a < b ? a : b;
}
void build(const vector<T>& a) {
n = a.size();
if (!n) return;
size = (n + B - 1) / B;
m = size * B;
h = 32 - __builtin_clz(size);
st.assign(h, vector<T>());
st[0].resize(size);
val.assign(m, id());
pre.assign(m, id());
suf.assign(m, id());
for (uint32_t i = 0; i < n; ++i) {
val[i] = a[i];
pre[i] = (i % B == 0 ? val[i] : op(pre[i - 1], val[i]));
}
for (uint32_t i = 0; i < m; i += B) {
uint32_t R = i + B - 1;
suf[R] = val[R];
for (int j = R - 1; j >= (int)i; --j)
suf[j] = op(val[j], suf[j + 1]);
st[0][i / B] = suf[i];
}
for (int k = 1; k < h; ++k) {
int len = 1 << k;
int half = len >> 1;
st[k].resize(size - len + 1);
for (uint32_t i = 0; i + len <= size; ++i) {
st[k][i] = op(st[k - 1][i], st[k - 1][i + half]);
}
}
}
T query(int l, int r) {
uint32_t L = l, R = r;
uint32_t bL = L >> 4; // /16
uint32_t bR = R >> 4;
if (bL == bR) {
T res = val[L];
for (uint32_t i = L + 1; i <= R; ++i)
res = op(res, val[i]);
return res;
}
if (bL + 1 == bR)
return op(suf[L], pre[R]);
uint32_t lBlock = bL + 1;
uint32_t rBlock = bR - 1;
int len = rBlock - lBlock + 1;
int k = 31 - __builtin_clz(len);
T mid = op(st[k][lBlock],
st[k][rBlock - (1 << k) + 1]);
return op(op(suf[L], mid), pre[R]);
}
};
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
vector<int> a(n+1);
for(int i=1; i<=n; ++i) cin >> a[i];
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<=A; ++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; cin >> q;
while(q--) {
int l, r;
cin >> l >> r;
int res = 0;
vector<pair<int, int>> border;
vector<int> pref_sum;
border.push_back({l, 0});
pref_sum.push_back(0);
auto before_border = [&](int x) {
auto it = (int)border.size() - 1;
ll sum = prefix[border[it].second][x-1] - prefix[border[it].second][border[it].first-1] + pref_sum[it];
return sum;
};
for(int x=1; x<=A; ++x) {
int L = lower_bound(occ[x].begin(), occ[x].end(), l) - occ[x].begin();
int R = upper_bound(occ[x].begin(), occ[x].end(), r) - 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) - prefix[x][occ[x][R]-1] < 0) continue;
while(lo < hi) {
int mid = (lo+hi)/2;
int p = occ[x][mid];
int S = before_border(p);
int M = ds[x].query(p, r) - prefix[x][p-1];
if(S + min(0, M) < 0) lo = mid+1;
else hi = mid;
}
res += R-lo+1;
int p = occ[x][lo];
while(border.size() && border.back().first > p) {
border.pop_back();
pref_sum.pop_back();
}
pref_sum.push_back(pref_sum.back() + prefix[border.back().second][p-1] - prefix[border.back().second][border.back().first - 1]);
border.push_back({p, x});
}
cout << res << "\n";
}
return 0;
}
