#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int mxn = 4e5 + 5;
const int base = 74;
const int LOG = 3;
int n, m, pw[LOG];
int stab[LOG][mxn];
map<i64, int> mp;
map<i64, int>::iterator it;
int main() {
cin >> n;
mp[0] = 0;
long long pref = 0;
fill(stab[0], stab[0] + n + 5, n + 1);
for(int t, i = 1; i <= n; i++) {
cin >> t;
pref += t;
it = mp.find(pref);
if(it != mp.end()) {
// cout << it->second << ' ' << i << endl;
stab[0][it->second] = i;
}
mp[pref] = i;
}
for(int i = n; i >= 0; i--)
stab[0][i] = min(stab[0][i], stab[0][i + 1]);
pw[0] = 1;
for(int k = 1; k < LOG; k++) {
fill(stab[k], stab[k] + n + 5, n + 1);
pw[k] = pw[k - 1] * base;
for(int i = 1; i <= n; i++) {
int cur = stab[k - 1][i];
for(int b = 1; b < base; b++)
cur = stab[k - 1][cur];
stab[k][i] = cur;
}
}
cin >> m;
int l, r, ans = 0;
while(m--) {
cin >> l >> r;
ans = 0;
l--;
for(int k = LOG - 1; k >= 0; k--)
for(int b = 1; b < base; b++)
if(stab[k][l] <= r) {
l = stab[k][l];
ans += pw[k];
}
cout << ans << endl;
}
return 0;
}
