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