#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 using i64 = long long; template<typename T> using vec = vector<T>; int n,q; vec<int> a,pref; vec<vec<int>> binlift; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n; a.assign(n + 10,0); pref.assign(n + 10,0); binlift.assign(n + 10,vec<int>(11,n)); for (int i = 0; i < n; i++){ cin >> a[i]; pref[i+1] = a[i]; pref[i+1] += pref[i]; } map<int,int> mp; vec<int> nxt(n + 10,n + 1); for (int i = n; i > -1; i--){ if (mp.count(pref[i])){ nxt[i] = mp[pref[i]]; } mp[pref[i]] = i; } int mn = n + 1; for (int i = n; i > -1; i--){ mn = min(mn,nxt[i]); binlift[i][0] = mn; } // binlift[i][k] = i den 2 ^ (2 * k) ye kadar olan for (int k = 1; k <= 10; k++){ for (int i = 0; i <= n; i++){ int to = i; for (int j = 0; j < 4; j++){ to = binlift[to][k-1]; if (to == n + 1) break; } binlift[i][k] = to; } } int q; cin >> q; for (int qq = 0; qq < q; qq++){ int l,r; cin >> l >> r; l--; int ans = 0; for (int i = 20; i >= 0; i--){ int to = l,k = i / 2; if (i & 1){ for (int j = 0; j < 2; j++){ to = binlift[to][k]; if (to == n+1) break; } } else to = binlift[to][k]; if (to <= r){ l = to; ans += (1 << i); } } cout << ans << endl; } return 0; }