#include <bits/stdc++.h>
using namespace std;
// Use standard int for memory efficiency
// Only use long long for the actual prefix sums
typedef long long ll;
const int MAXN = 200005;
const int LOGN = 19; // 2^18 > 200,000, 19 is safe
const int INF_IDX = MAXN + 2;
// Static arrays are much lighter on memory than nested vectors
int jump[LOGN][MAXN];
ll pr[MAXN];
int a[MAXN];
void solve() {
int n;
if (!(cin >> n)) return;
// Use a hash map with a custom hash to avoid collisions and save memory
// Or just use map if memory allows after fixing the jump table
unordered_map<ll, int> mp;
pr[0] = 0;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
pr[i] = pr[i-1] + a[i];
}
int pos_zero = INF_IDX;
mp[pr[n]] = n + 1;
// Set base cases for the jump table
for(int j = 0; j < LOGN; j++) jump[j][n+1] = INF_IDX;
for (int i = n; i >= 1; --i) {
if (a[i] == 0) pos_zero = i + 1;
int best = jump[0][i+1];
// A segment [i, k] has sum 0 if pr[k] == pr[i-1]
if (mp.count(pr[i-1])) {
best = min(best, mp[pr[i-1]]);
}
best = min(best, pos_zero);
jump[0][i] = best;
mp[pr[i-1]] = i; // Store the earliest occurrence for the next iterations
// Re-filling mp correctly: we need the smallest index j > i such that pr[j] == pr[i-1]
// Actually, the logic in your original loop was slightly reversed.
// Let's fix the map update:
mp[pr[i]] = i + 1;
}
// Binary Lifting Table construction
for (int j = 1; j < LOGN; ++j) {
for (int i = 1; i <= n + 1; ++i) {
int nxt = jump[j-1][i];
if (nxt <= n + 1)
jump[j][i] = jump[j-1][nxt];
else
jump[j][i] = INF_IDX;
}
}
int q;
cin >> q;
while(q--) {
int l, r;
cin >> l >> r;
int cur = l;
int ans = 0;
for (int j = LOGN - 1; j >= 0; --j) {
if (cur <= n && jump[j][cur] <= r + 1) {
ans += (1 << j);
cur = jump[j][cur];
}
}
cout << ans << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}
