#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int mxn = 4e5, base = 74;
int n, q;
int up[mxn + 1][3], a[mxn + 1], pw[3];
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++)cin >> a[i];
unordered_map<ll, int>mp; mp[0] = n + 1;
ll sm = 0;
for(int i = n; i >= 1; i--){
sm += 1LL * a[i];
if(mp.find(sm) != mp.end()){
a[i] = mp[sm] - 1;
}else{
a[i] = n + 1;
}
mp[sm] = i;
}
mp.clear();
int mn = n + 1;
up[n + 1][0] = n + 1;
for(int i = n; i >= 1; i--){
mn = min(mn, a[i]);
up[i][0] = mn;
}
for(int i = 1; i < 3; i++){
for(int j = 1; j <= n + 1; j++){
int v = j;
for(int k = 0; k < base; k++){
v = up[v][i - 1] + 1;
if(v >= n + 1){
v = n + 2; break;
}
}
up[j][i] = v - 1;
//cout << i << " " << j << ' ' << up[j][i] << "\n";
}
}
pw[0] = 1;
for(int i = 1; i < 3; i++)pw[i] = pw[i - 1] * base;
cin >> q;
while(q--){
int l, r; cin >> l >> r;
int ans = 0;
for(int i = 2; i >= 0; i--){
while(1){
if(up[l][i] <= r){
ans += pw[i]; l = up[l][i] + 1;
}else{
break;
}
}
}
cout << ans << "\n";
}
return(0);
}
