#include <bits/stdc++.h> using namespace std; int dfs(int s, vector<int> const&child, vector<int> const& start, vector<int>& heavy) { int sz = 1; int chmax = 0; for(int i = start[s]; i < start[s + 1]; i ++) { int ch = child[i]; int chsz = dfs(ch, child, start, heavy); sz += chsz; if(chsz > chmax) { heavy[s] = ch; chmax = chsz; } } return sz; } void decompose(int s, int h, vector<int> const&child,vector<int> const& start, vector<int>const& heavy, vector<int>& head, vector<int>& pos, int& curpos) { head[s] = h, pos[s] = curpos++; if(heavy[s] != -1) decompose(heavy[s], h, child, start, heavy, head, pos, curpos); for(int i = start[s]; i < start[s + 1]; i ++) { int ch = child[i]; if(ch != heavy[s]) { decompose(ch, ch, child, start, heavy, head, pos, curpos); } } } signed main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; vector<int> next(n + 1); next[n] = INT_MAX; { vector<int> a(n); vector<int> pref(n + 1); pref[0] = 0; unordered_map<int, int> mp; for(auto &x:a) cin >> x; for(int i = 0; i < n; i ++) pref[i + 1] = pref[i] + a[i]; for(int i = n - 1; i >= 0; i --) { mp[pref[i + 1]] = i; if(mp.count(pref[i])) next[i] = min(mp[pref[i]], next[i + 1]); else next[i] = next[i + 1]; } pref.clear(); pref.shrink_to_fit(); a.clear(); a.shrink_to_fit(); mp.clear(); } // garbage collection vector<int> head(n + 1, 0), pos(n + 1, -1); { vector<int> child(n+ 1, 0); vector<int> start (n + 2, 0); vector<int> degree(n + 2, 0); for(int i = 0; i <= n; i ++) { if(next[i] < n && next[i] >= 0) degree[next[i] + 1]++; } start[0] = 0; for(int i = 0; i <=n + 1; i ++) start[i] = start[i - 1] + degree[i - 1]; vector<int> cur = start; for(int i = 0; i < n; i ++) if(next[i] < n && next[i] >= 0) child[cur[next[i] + 1]++] = i; cur.clear(); cur.shrink_to_fit(); next.clear(); next.shrink_to_fit(); vector<int> heavy(n + 1, -1); { int cp = 0; for(int i = n; i >= 0; i --) { if(pos[i] != -1) continue; dfs(i, child, start, heavy); decompose(i, i, child, start, heavy, head, pos, cp); } } heavy.clear(); heavy.shrink_to_fit(); degree.clear(); degree.shrink_to_fit(); next.assign(n + 1, -1); for(int i = 0; i <= n; i ++) { for(int j = start[i]; j < start[i + 1]; j ++) { next[child[j]] = i - 1; } } start.clear(); start.shrink_to_fit(); child.clear(); child.shrink_to_fit(); } // garbage collection vector<int> revpos(n + 1); for(int i = 0; i <= n; i ++) revpos[pos[i]] = i; for(int i = 0; i <= n; i ++) { if(next[i] == -1 || next[i] == INT_MAX) next[i] = -1; else next[i]++; } int q; cin >> q; while(q--) { int l, r; cin >> l >> r; l --; int curl = l; int curd = 0; while(true) { if(head[curl] <= r) { if(next[head[curl]] < 0) { curd += pos[curl] - pos[head[curl]]; curl = head[curl]; break; } else { curd += pos[curl] - pos[head[curl]]+ 1; curl = next[head[curl]]; } } else break; } if(head[curl] == curl && next[curl] < 0) { if(curl > r) cout << "0\n"; else cout << curd << '\n'; continue; } int ll = pos[head[curl]], rr = pos[curl]; int ans = INT_MAX; while(ll <= rr) { int m = (ll + rr) >> 1; if(revpos[m] <= r) { rr = m - 1; ans = min(ans, m); } else { ll = m + 1; } } if(ans == INT_MAX) cout << max(0, curd - 1) << '\n'; else cout << curd + pos[curl] - ans << '\n'; } }