#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using ordered_set = tree< T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") //#pragma GCC target("avx,avx2,fma") #define ld long double #define F first #define S second #define all(v) v.begin(),v.end() #define pb push_back #define eb emplace_back #define endl '\n' #define pqueue priority_queue typedef pair<int,int> ii; using i64 = long long; template<typename T> using vec = vector<T>; int n,q; vec<int> a; int BLOCK_SIZE; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n; a.assign(n+1,0); vec<int> lift1(n+1); vec<int> lift2(n+1); BLOCK_SIZE = 10; for (int i = 1; i <= n; i++){ cin >> a[i]; a[i] += a[i-1]; } map<int,int> mp; vec<int> nxt(n+1,n + 1); for (int i = n; i > -1; i--){ if (mp.count(a[i])){ nxt[i] = mp[a[i]]; } mp[a[i]] = i; } int mn = n + 1; for (int i = n; i > -1; i--){ mn = min(mn,nxt[i]); lift1[i] = mn; } for (int k = 1; k <= BLOCK_SIZE; k++){ int use = 1; if (k == 1) use = 0; for (int i = 0; i <= n; i++){ int to = i; for (int j = 0; j < 2; j++){ if (k == 1) to = lift1[to]; else to = lift2[to]; if (to == n + 1) break; } lift2[i] = to; } } int q; cin >> q; for (int qq = 0; qq < q; qq++){ int l,r; cin >> l >> r; l--; int ans = 0; while (lift2[l] <= r){ l = lift2[l]; ans += (1 << BLOCK_SIZE); } while (lift1[l] <= r){ l = lift1[l]; ans++; } cout << ans << endl; } return 0; }