#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 lift(int node,int k){ for (int i = 0; i <= 30; i++){ if (k & (1 << i)){ node = binlift[node][i]; if (node == n+1) return node; } } return node; } 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>(32,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; } for (int k = 1; k <= 30; k++){ for (int i = 0; i <= n; i++){ int to = binlift[i][k-1]; if (to == n + 1) binlift[i][k] = to; else binlift[i][k] = binlift[to][k-1]; } } int q; cin >> q; for (int qq = 0; qq < q; qq++){ int l,r; cin >> l >> r; l--; int s = 0,e = n + 1,ans = 0; while (s <= e){ int m = (s+e) / 2; //cerr << s << " " << e << " " << m << " " << lift(l,m) << endl; if (lift(l,m) <= r) { ans = m; s = m+1; } else e = m-1; } cout << ans << endl; } return 0; }