// I also thought that there was a small chance that she likes me back. #include <bits/stdc++.h> using namespace std; // Do you think you'll ever remember me someday, or will I just fade away from your memory? #define LIFESUCK ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll long long #define str string #define mll map<ll, ll> #define vll vector<ll> #define pll pair<ll, ll> #define fi first #define se second #define all(c) c.begin(), c.end() #define pb push_back #define sz(s) s.size() #define debug cout << "I Love You\n"; #define fu(i, a, b) for (ll i = a; i <= b; i++) #define fd(i, b, a) for (ll i = b; i >= a; i--) #define Bitc(msk, j) ((msk >> j) & 1) #define _log(x) 31 - __builtin_clz(x) #define LoveTime chrono::steady_clock::now().time_since_epoch().count() const ll Mod = 1e9 + 7; const ll inf = (1ll << 30); const ll lnf = (1ll << 60); // When time passes and things change... will you still remember someone like me? int64_t add(ll& a, ll b) { a += b; if (a >= Mod) a %= Mod; while (a < 0) a += Mod; return a; } int64_t mul(ll a, ll b) { a = 1ll * a * b % Mod; return a; } template <class X, class Y> bool minimize(X& x, Y y) { X eps = 1e-9; if (x > y + eps) { x = y; return 1; } return 0; } template <class X, class Y> bool maximize(X& x, Y y) { X eps = 1e-9; if (x + eps < y) { x = y; return 1; } return 0; } // I wonder… will I just become a distant memory to you one day? #define mxn 400'007 ll n, q, g[mxn]; struct Quest { ll l, r; } Qu[mxn]; namespace Love1 { bool chk() { return (n <= 5000 && q <= 5000); } void DreamyLove () { mll mp; fu(qst, 1, q) { auto[l, r] = Qu[qst]; ll sum = 0, cr = 0; mp.clear(); mp[0] = 1; fu(i, l, r) { sum += g[i]; if(mp.find(sum) != mp.end()) { mp.clear(); cr++; sum = 0; } mp[sum] = 1; } cout << cr << '\n'; } // } }; namespace LoveLast { ll nxt[mxn]; ll f[21][mxn]; void DreamyLove () { mll mp; mp[0] = n + 1; nxt[n + 1] = n + 2; nxt[n + 2] = n + 2; ll sum = 0; fd(i, n, 1) { sum += g[i]; if(mp.find(sum) == mp.end()) nxt[i] = nxt[i + 1]; else nxt[i] = min(mp[sum], nxt[i + 1]); mp[sum] = i; } fu(i, 1, n + 2) f[0][i] = nxt[i]; fu(j, 1, 19) fu(i, 1, n + 2) { ll jmp = f[j - 1][i]; if(jmp <= n + 2) f[j][i] = f[j - 1][f[j - 1][i]]; else f[j][i] = n + 2; } fu(qst, 1, q) { auto[l, r] = Qu[qst]; ll sad = 0; fd(j, 19, 0) if(f[j][l] <= r + 1) sad += (1 << j), l = f[j][l]; cout << sad << '\n'; } // } }; // The world is still beautiful, only it’s a pity that you are no longer among the living. void lovesper(const ll& TestCase) { cin >> n; fu(i, 1, n) cin >> g[i]; cin >> q; fu(qst, 1, q) cin >> Qu[qst].l >> Qu[qst].r; // if(Love1::chk()) { // Love1::DreamyLove(); // return; // } LoveLast::DreamyLove(); } // In the future, each of us will have our own path.. // ...But no matter where we go, we will always be a beautiful part of each other’s memories. signed main() { LIFESUCK #define name "lovesper" // freopen(name".inp", "r", stdin); // freopen(name".out", "w", stdout); ll Test = 1; // cin >> Test; fu(i, 1, Test) { lovesper(i); if (i < Test) cout << '\n'; } return 0; }