#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; }