#include <bits/stdc++.h> using namespace std; #define sz(x) (int)x.size() #define all(x) x.begin() , x.end() const int SQRT = 632; void solve(){ int n; cin >> n; vector<int>jump1(n+1,n+1); { { vector<long long>pre(n+1,0); for(int i = 1;i<=n;i++){ cin >> pre[i]; pre[i] += pre[i-1]; } map<long long,int>mpa; for(int i = n;i>=0;i--){ if(mpa.count(pre[i])){ jump1[i] = mpa[pre[i]]; } mpa[pre[i]] = i; } } for(int i = n-1;i>=0;i--){ jump1[i] = min(jump1[i] , jump1[i+1]); } } vector<int> jump2(n+1,-1); { vector<int>tree[n+2]; for(int i = 0;i<=n;i++){ tree[jump1[i]].push_back(i); } deque<int>path; function<void(int)> dfs = [&](int node){ if(sz(path) == SQRT){ jump2[node] = path[0]; path.pop_front(); } path.push_back(node); for(auto itr : tree[node]){ dfs(itr); } if(path[0] != n+1){ path.push_front(jump1[path[0]]); } path.pop_back(); }; dfs(n+1); } int q; cin >> q; while(q--){ int l,r; cin >> l >> r; l--; int ans = 0; while(l <= n and jump2[l] <= r and jump2[l] != -1){ ans += SQRT; l = jump2[l]; } while(l <= n and jump1[l] <= r and jump1[l] != -1){ ans++; l = jump1[l]; } cout << ans << '\n'; } } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0); int testcase=1;//cin >> testcase; while(testcase--)solve(); cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl; }