#include <bits/stdc++.h> using namespace std; typedef long long ll; // Use slightly larger bounds to prevent off-by-one errors const int MAXN = 200007; const int LOGN = 20; const int INF_IDX = 200005; int jump[LOGN][MAXN]; ll pr[MAXN]; int a[MAXN]; void solve() { int n; if (!(cin >> n)) return; // Use a standard map for safety; if it TLEs, we use a custom hash map<ll, int> mp; pr[0] = 0; for(int i = 1; i <= n; ++i) { cin >> a[i]; pr[i] = pr[i-1] + a[i]; } // Initialize jump table with a value representing "out of bounds" for(int j = 0; j < LOGN; j++) { for(int i = 0; i <= n + 2; i++) { jump[j][i] = n + 1; } } int next_occurrence = n + 1; mp[pr[n]] = n; // Precomputing jump[0][i]: The first point where a zero-sum subarray ends // starting from index i or later. for (int i = n; i >= 1; --i) { // Option 1: A zero-sum subarray already exists further to the right next_occurrence = jump[0][i+1]; // Option 2: A zero-sum subarray ends right here (if a[i] == 0) if (a[i] == 0) { next_occurrence = min(next_occurrence, i); } // Option 3: A zero-sum subarray starts at i and ends at some k // This happens if pr[k] == pr[i-1] if (mp.find(pr[i-1]) != mp.end()) { next_occurrence = min(next_occurrence, mp[pr[i-1]]); } jump[0][i] = next_occurrence; mp[pr[i-1]] = i - 1; // Update map with the leftmost occurrence of this sum } // Binary Lifting Table Construction for (int j = 1; j < LOGN; ++j) { for (int i = 1; i <= n; ++i) { int mid = jump[j-1][i]; if (mid < n) { // If we found a zero-sum range ending at 'mid', // the next one must start at 'mid + 1' jump[j][i] = jump[j-1][mid + 1]; } else { jump[j][i] = n + 1; } } } 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 the j-th jump starts at 'cur' and ends within 'r' if (cur <= r && jump[j][cur] <= r) { ans += (1 << j); cur = jump[j][cur] + 1; // Next subarray must start after this one ends } } cout << ans << '\n'; } } int main() { // Fast I/O is essential for 2e5 inputs ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }