#include <bits/stdc++.h>
using namespace std;
// #pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3,no-stack-protector,conserve-stack")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair
const int LOG = 3;
const int base = 74;
const int mxn = 4e5 + 10;
int i, j, n, m;
long long pref;
map<long long, int> mp;
int stab[mxn][LOG];
int pw[LOG];
int main() {
#ifdef LOCAL
auto start = chrono::high_resolution_clock::now();
#endif
cin.tie(0)->sync_with_stdio(0);
cin >> n;
mp[0] = 0;
for(i = 1; i <= n; i++) {
cin >> j;
pref += j;
auto it = mp.find(pref);
if(it != mp.end()) {
stab[it->ss + 1][0] = i;
}
mp[pref] = i;
}
mp.clear();
for(i = n; i > 0; i--) {
if(stab[i][0] == 0)
stab[i][0] = stab[i + 1][0];
else if(stab[i + 1][0] > 0)
stab[i][0] = min(stab[i][0], stab[i + 1][0]);
}
int cur, b;
for(j = 1; j < LOG; j++)
for(i = 1; i <= n; i++) {
cur = stab[i][j - 1];
for(b = 1; b < base; b++) {
if(cur > 0 && cur + 1 <= n)
cur = stab[cur + 1][j - 1];
else {
cur = 0;
break;
}
}
stab[i][j] = cur;
}
pw[0] = 1;
for(int i = 1; i < LOG; i++)
pw[i] = pw[i - 1] * base;
cin >> m;
int l, r, ans;
while(m--) {
cin >> l >> r;
ans = 0;
for(j = LOG - 1; j >= 0; j--) {
while(stab[l][j] > 0 && stab[l][j] <= r) {
l = stab[l][j] + 1;
ans += pw[j];
}
}
cout << ans << endl;
}
#ifdef LOCAL
auto end = chrono::high_resolution_clock::now();
for(int i = 0; i <= 20; ++i) cout << '-';
cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif
return 0;
}
