#pragma GCC optimize("O3,unroll-loops") #include <bits/stdc++.h> using namespace std; using ll = long long; // ----------- Constants ------------ static const ll INF = (ll)1e18; // ----------- Main Solve Function ------------ void solve() { int n; cin >> n; vector<ll> a(n + 1), pref(n + 1, 0); for (int i = 1; i <= n; i++) { cin >> a[i]; pref[i] = pref[i - 1] + a[i]; } // compute LOG dynamically int LOG = 1; while ((1LL << LOG) <= n) LOG++; // flat jump table: LOG * (n+2) vector<int> jump(LOG * (n + 2), -1); auto J = [&](int j, int i) -> int& { return jump[j * (n + 2) + i]; }; map<ll, int> mp; // base case J(0, n) = n + 1; mp[pref[n]] = n; // build jump[0][i] for (int i = n - 1; i >= 1; i--) { auto it = mp.find(pref[i - 1]); if (it == mp.end()) { J(0, i) = J(0, i + 1); } else { int pos = it->second; if (J(0, i + 1) == -1) J(0, i) = pos; else J(0, i) = min(J(0, i + 1), pos); } mp[pref[i]] = i; } // binary lifting for (int j = 1; j < LOG; j++) { for (int i = 1; i <= n; i++) { int nxt = J(j - 1, i); if (nxt != -1 && nxt <= n + 1) { J(j, i) = J(j - 1, nxt); } } } int q; cin >> q; while (q--) { int l, r; cin >> l >> r; int cur = l; ll ans = 0; for (int j = LOG - 1; j >= 0; j--) { int nxt = J(j, cur); if (nxt != -1 && nxt <= r) { ans += (1LL << j); cur = nxt; } } cout << ans << '\n'; } } // ----------- Main Function ------------ int main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }