// 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 int
#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;
}
