// good problem
// given a array and queries (l,r) we need to find the mimimum number of segments to split subarray [l,r]
// so that each subsegment has hcf as 1 .
// https://codeforces.com/contest/1516/problem/D
// used array to calculate prime factors of a number
// didnt construct the tree and directly found the lift
// as the tree when rooted at n+1 for all where numbers of depth i is less than nodes of depth i-1
// so, ansector of a node if always higher than it .
// so when constructing lift construct from root (n+1) and decrease to 1 .
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef set<pii> sii ;
typedef vector<int> vi ;
typedef multiset<int, greater<int> > msi ;
typedef set<int> si ;
#define FOR(i,b) for (int i=0; i<b; i++)
#define FORB(i,a,b) for (int i=int(a); i<(int)b; i++)
#define FOR3(l,w,h) FOR(i,l) FOR(j,w) FOR(k,h)
#define FOR2(l,w) FOR(i,l) FOR(j,w)
#define inf 1e8 + 1
const int N = (int) 4e5 +1 ;
int arr[N] ;
int lift[N][20] ;
int zeros[N] ;
int par[N] ;
unordered_map<ll , int> sums ;
int main() {
memset(zeros,-1,sizeof(zeros));
int n , q ;
cin>>n ;
FOR(i,n) cin>>arr[i] ;
cin>>q ;
ll sum = 0 ;
zeros[0] = -1 ;
FOR(i,n) {
sum += (ll) arr[i] ;
if ( sums.find(sum) != sums.end() ) {
zeros[sums[sum] + 1] = i ;
}
if ( sum == 0 && zeros[0] == -1 ) zeros[0] = i ;
sums[sum] = i ;
}
// FOR(i,n) cout<<zeros[i]<<" " ;
// cout<<endl ;
int last_zero = -1 ;
int n_max = -1 ;
for(int i = n-1 ; i >= 0 ; i-- ) {
if ( last_zero == -1 ) {
if ( zeros[i] != -1 ) last_zero = zeros[i] + 1 ;
} else {
if ( zeros[i] != -1 )
last_zero = min(last_zero, zeros[i] + 1) ;
}
if ( last_zero != -1 ) n_max = max(n_max,last_zero) ;
par[i] = last_zero ;
}
// FOR(i,n) cout<<par[i]<<" " ;
// cout<<endl ;
memset(lift,-1,sizeof(lift));
if ( n_max >= 0 ) {
FOR (i,20) lift[n_max][i] = -1 ;
for ( int i = n_max - 1 ; i >= 0 ; i-- ) {
lift[i][0] = par[i] ;
// if ( i == 1 ) cout<<endl<<lift[i][0]<<endl ;
for ( int j = 1 ; j < 20 ; j++ ) {
if ( lift[i][j-1] == -1 ) lift[i][j] = -1 ;
else lift[i][j] = lift[lift[i][j-1]][j-1] ;
}
}
}
while ( q-- ) {
int l , r ;
cin>>l>>r ;
l-- ; r-- ;
int k = 0 ;
if(l > r) {cout << "0\n"; continue;}
for ( int i = 19 ; i >= 0 ; i-- ) {
// cout<<lift[l][i]<<" "<<l<<" "<<i<<" "<<r<<endl ;
if ( lift[l][i] == -1 ) continue ;
if ( lift[l][i] <= r + 1 ) {
l = lift[l][i] ;
k += (1<<i) ;
}
}
cout<<k<<endl ;
}
}
