#include<bits/stdc++.h> #pragma GCC optimize("unroll-loops,O3") using namespace std; using i64 = long long; //#define int i64 #define vi vector<int> #define vvi vector<vi> #define vb vector<bool> #define se second #define fi first #define pii pair<int, int> #define sz(x) (int)(x).size() const int LG = 20; inline void solve(){ int n, q; cin >> n; vi a(n); for(int i = 0; i < n; i++){ cin >> a[i]; } map<i64, int> sufi; sufi[0] = n - 1; i64 s = 0; vvi lift(2, vi(n + 2)); vi go(n + 2); go[n] = go[n + 1] = lift[0][n] = lift[0][n + 1] = n + 1; for(int i = n - 1; i >= 0; i--){ s += a[i]; a.pop_back(); if(sufi.count(s)){ lift[0][i] = sufi[s] + 1; } else{ lift[0][i] = n + 1; } sufi[s] = i - 1; go[i] = lift[0][i] = min(lift[0][i], lift[0][i + 1]); //cout << "i: " << i << " go: " << lift[i][0] << " s: " << s << "\n"; } sufi.clear(); cin >> q; vector<pii> queries(q); vi ans(q); auto checklg = [&](int lg) -> void { lift[0] = go; for(int bit = 1; bit <= lg; bit++){ for(int v = n + 1; v >= 0; v--){ lift[1][v] = lift[0][lift[0][v]]; if(v <= n) lift[1][v] = min(lift[1][v], lift[1][v + 1]); } lift[0].swap(lift[1]); } for(int i = 0; i < q; i++){ if(lift[0][queries[i].fi] - 1 <= queries[i].se){ queries[i].fi = lift[0][queries[i].fi]; ans[i] |= (1 << lg); } } return; }; for(int i = 0; i < q; i++){ int l, r; cin >> l >> r; l--, r--; queries[i] = {l, r}; } for(int bit = LG - 1; bit >= 0; bit--){ checklg(bit); } for(int i = 0; i < q; i++){ cout << ans[i] << "\n"; } return; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int t = 1; //cin >> t; while(t--){ solve(); } return 0; }