#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; vector<i64> 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(n + 2, vi(LG)); lift[n][0] = lift[n + 1][0] = n + 1; for(int i = n - 1; i >= 0; i--){ s += a[i]; if(sufi.count(s)){ lift[i][0] = sufi[s] + 1; } else{ lift[i][0] = n + 1; } sufi[s] = i - 1; lift[i][0] = min(lift[i][0], lift[i + 1][0]); //cout << "i: " << i << " go: " << lift[i][0] << " s: " << s << "\n"; } for(int bit = 1; bit < LG; bit++){ for(int v = n + 1; v >= 0; v--){ lift[v][bit] = lift[lift[v][bit - 1]][bit - 1]; if(v <= n) lift[v][bit] = min(lift[v][bit], lift[v + 1][bit]); } } auto query = [&](int l, int r) -> int { int ret = 0, cur = l; for(int bit = LG - 1; bit >= 0; bit--){ //cout << "bit: " << bit << " cur: " << cur << " go: " << lift[cur][bit] << "\n"; if(lift[cur][bit] - 1 <= r){ cur = lift[cur][bit]; ret |= (1 << bit); } } return ret; }; cin >> q; while(q--){ int l, r; cin >> l >> r; l--, r--; cout << query(l, r) << "\n"; } return; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int t = 1; //cin >> t; while(t--){ solve(); } return 0; }