#include <bits/stdc++.h>
using namespace std;
unordered_map <long long, int> f;
const int NMAX = 4e5;
const int LOG4MAX = 9;
int max_left[NMAX + 1][LOG4MAX + 1]; /// max_left[i][j] cel mai mare k pentru care exista 2^j subsecvente de suma 0 intre k si i.
void calc_max_left() {
long long s = 0;
int n, x;
cin >> n;
for ( int i = 1; i <= n; i ++ ) {
cin >> x;
s += x;
if ( f[s] == 0 && s != 0 ) max_left[i][0] = max_left[i - 1][0];
else max_left[i][0] = max( max_left[i - 1][0], f[s] + 1 );
f[s] = i;
}
for ( int i = 1; i <= n; i ++ ) {
for ( int j = 1; ( 1 << ( 2 * j ) ) <= i; j ++ ) {
int x = i + 1;
for ( int k = 1; k <= 4; k ++ ) {
x = max_left[x - 1][j - 1];
if ( x == 0 ) {
x = -1;
break;
}
}
max_left[i][j] = x + 1;
}
}
}
int main() {
ios_base::sync_with_stdio( false );
cin.tie( NULL );
int q;
calc_max_left();
cin >> q;
for ( int i = 1; i <= q; i ++ ) {
int l, r, p4 = LOG4MAX, ans = 0;
cin >> l >> r;
while ( r >= l ) {
while ( p4 >= 0 && max_left[r][p4] < l ) p4 --;
if ( p4 >= 0 ) {
ans += ( 1 << ( 2 * p4 ) );
r = max_left[r][p4] - 1;
} else {
r = 0;
}
}
cout << ans << '\n';
}
return 0;
}
