// 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 = 1e5 + 3 ;
const int K = 18 ;
int arr[N] ;
int zeros[N] ;
int par[N] ;
int lift[N] ;
int ans[N] ;
pii req[N];
int n , q ;
void solve(int ll) {
for ( int k = 0 ; k <= ll ; k++ ) {
for ( int i = 0 ; i < n ; i++ ) {
if ( k == 0 ) lift[i] = par[i] ;
else {
if ( lift[i] != -1 ) lift[i] = lift[lift[i]] ;
}
}
}
FOR(i,q) {
auto &[l,r] = req[i] ;
// cout<<i<<" "<<l<<" "<<r<<" "<<ll<<endl ;
if(l > r || l > n-1) { continue; }
if ( l == -1 ) break ;
if ( lift[l] == -1 ) continue ;
if ( lift[l] <= r + 1 ) {
l = lift[l] ;
ans[i] += (1<<ll) ;
}
}
}
unordered_map<ll , int> sums ;
int main() {
// const int N = (int) 2e5 +5 ;
cin>>n ;
memset(zeros,-1,sizeof(zeros));
memset(ans,0,sizeof(ans));
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 ;
memset(par,-1,sizeof(par));
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));
FOR(i,q) {
int l , r ;
cin>>l>>r ;
l-- ; r-- ;
req[i] = {l,r} ;
}
for(int i = K-1 ; i >= 0 ; i--) solve(i) ;
FOR(i,q) {
cout<<ans[i]<<endl ;
}
}
