// GPT changed it to 5 lifting
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;
const int LOG = 10; // 5^9 > 4e5
int up[N][LOG];
int idx[N];
long long pw[LOG];
void solve() {
int n;
cin >> n;
pw[0] = 1;
for (int i = 1; i < LOG; i++) pw[i] = pw[i - 1] * 5;
for (int i = 0; i <= n; i++) idx[i] = 1e9;
map<int, int> last;
int pre = 0;
for (int i = 0; i <= n; i++) {
if (i) {
int x;
cin >> x;
pre += x;
}
if (last.count(pre)) up[i][0] = last[pre];
else up[i][0] = -1;
last[pre] = i;
if (up[i][0] != -1) idx[up[i][0]] = min(idx[up[i][0]], i);
}
int mn = 1e9;
for (int i = n; i >= 0; i--) {
if (idx[i] != 1e9) mn = min(mn, idx[i]);
if (mn == 1e9) up[i][0] = n + 1;
else up[i][0] = mn;
for (int k = 1; k < LOG; k++) {
int a = up[i][k - 1];
if (a > n) {
up[i][k] = n + 1;
continue;
}
int b = up[a][k - 1];
if (b > n) {
up[i][k] = n + 1;
continue;
}
int c = up[b][k - 1];
if (c > n) {
up[i][k] = n + 1;
continue;
}
int d = up[c][k - 1];
if (d > n) {
up[i][k] = n + 1;
continue;
}
up[i][k] = up[d][k - 1];
}
}
int q;
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
l--;
long long ans = 0;
for (int b = LOG - 1; b >= 0; b--) {
for (int rep = 0; rep < 4; rep++) { // base 5 digit: 0..4
if (up[l][b] > r) break;
ans += pw[b];
l = up[l][b];
}
}
cout << ans << '\n';
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
