#include <bits/stdc++.h>
using namespace std;
// Define long long for prefix sums as values can exceed 2^31
typedef long long ll;
// Constraints: N <= 400,000.
// We use 400,005 for safety.
const int MAXN = 400005;
const int LOGN = 20; // 2^19 > 400,000, so 20 is plenty safe.
// Global arrays to prevent stack overflow
int jump[LOGN][MAXN];
ll pr[MAXN];
int n, q;
void solve() {
if (!(cin >> n)) return;
// Reading input and building prefix sums
// pr[i] stores the sum of c[1]...c[i]
pr[0] = 0;
for(int i = 1; i <= n; ++i) {
int val;
cin >> val;
pr[i] = pr[i-1] + val;
}
cin >> q;
// 'mp' stores the LAST seen position of a prefix sum while iterating backwards.
// Effectively, for current index 'i', it tells us the nearest 'j' >= i such that pr[j] == val.
map<ll, int> mp;
// Initialize the 'infinity' limit
// If a subarray ends at 'n', the next one would start at 'n+1'.
// So 'n+2' is a safe "infinity" / "no solution" marker.
int INF = n + 2;
// Initialize base cases for binary lifting beyond valid range
for(int j = 0; j < LOGN; j++) {
jump[j][n + 1] = INF;
jump[j][n + 2] = INF;
}
// We keep track of the earliest ending position of a valid zero-sum subarray
// found so far to the right.
int min_end = INF;
// Fill mp with the final prefix sum to handle cases where a subarray ends at N
mp[pr[n]] = n;
// Iterate backwards to build the first level of the jump table (jump[0])
// jump[0][i] = (end index of the nearest zero-sum subarray starting >= i) + 1
for(int i = n; i >= 1; --i) {
// Check if there is a prefix sum P[j] == P[i-1] to the right
// If yes, a zero-sum subarray exists from i to j.
if (mp.count(pr[i-1])) {
int segment_end = mp[pr[i-1]];
min_end = min(min_end, segment_end);
}
// jump[0][i] points to the start of the NEXT disjoint subarray.
// If the best segment we found ends at 'min_end', the next one starts at 'min_end + 1'.
jump[0][i] = min_end + 1;
// Update map: current 'i' is now the leftmost occurrence of pr[i] seen so far
// (but actually we need to store pr[i] for the future iterations i-1, i-2...)
// effectively, mp[val] always stores the smallest index k >= current_i with pr[k] == val
mp[pr[i-1]] = i - 1; // Correct logic is to store the index for P[i-1] check?
// No, wait. For the NEXT iteration (i-1), we want to find P[(i-1)-1].
// The current iteration establishes P[i] is at index i.
// Actually, the simple logic is:
// We just processed index i. We want to make sure P[i-1] is available for future lookups of P[something] == P[i-1].
// But actually, we only need to update the map with the current prefix sum `pr[i-1]`
// is NOT relevant for the right side matching. We need to add `pr[i-1]` as a potential END point for a subarray starting to the left?
// No.
// Let's re-verify map update logic:
// A subarray starting at 'start' ends at 'end' if pr[end] == pr[start-1].
// When we are at 'i', we are the 'start'. We look for 'end' > 'i' such that pr[end] == pr[i-1].
// So we need the map to store positions of pr values to the RIGHT.
// So at step 'i', we should add `pr[i-1]` to the map? No, `pr[i-1]` is the value BEFORE index i.
// We are looking for a match to the right. The values to the right are `pr[i], pr[i+1]...`.
// So we should have added `pr[i]` to the map in the PREVIOUS iteration (i+1).
// Correct Loop Structure:
// 1. Calculate best match for current 'i'. Match is found if `pr[i-1]` exists in map.
// 2. Update `min_end`.
// 3. Update map with `pr[i-1]`? No! `pr[i-1]` is a potential END point for a subarray starting at `i-something`.
// But here we are moving left.
// Ah, the map must store indices `k` where `pr[k]` exists.
// At start of loop `i`, map contains indices `k > i`.
// We check `pr[i-1]`.
// Before going to `i-1`, we must add index `i-1` to the map?
// No, index `i-1` is an END point for a subarray starting at `Left`.
// So yes, we add `pr[i-1]` at index `i-1`.
mp[pr[i-1]] = i - 1;
}
// Binary Lifting Construction
// jump[j][i] is the starting position of the subarray after 2^j segments have been picked
for(int j = 1; j < LOGN; ++j) {
for(int i = 1; i <= n + 1; ++i) {
int mid = jump[j-1][i];
if(mid > n + 1) jump[j][i] = INF;
else jump[j][i] = jump[j-1][mid];
}
}
// Process Queries
while(q--) {
int l, r;
cin >> l >> r;
int ans = 0;
int curr = l;
for(int j = LOGN - 1; j >= 0; --j) {
// We want to jump 2^j steps.
// jump[j][curr] gives the START position of the (2^j + 1)-th segment.
// If that start position is valid (meaning the 2^j-th segment ended <= r), we take it?
// Wait, the definition: jump[j][curr] is the start of the next segment
// AFTER consuming 2^j segments starting from curr.
// So if jump[j][curr] - 1 <= r, it means all 2^j segments fit completely within [l, r].
if(jump[j][curr] <= r + 1) {
// Why r+1?
// jump[j][curr] is the start of the (2^j + 1)-th segment.
// The previous segment ended at jump[j][curr] - 1.
// We need that end <= r.
// So jump[j][curr] - 1 <= r => jump[j][curr] <= r + 1.
ans += (1 << j);
curr = jump[j][curr];
}
}
cout << ans << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
