#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int maxn = 1e6 + 7 ;
inline ll read(){
	ll x = 0 , f = 1 ;
	char c = getchar() ;
	while(c > '9' || c < '0'){
		if(c == '-')
			f = -1 ;
		c = getchar() ;
	}
	while(c >= '0' && c <= '9'){
		x = x * 10 + c - '0' ;
		c = getchar() ;
	}
	return x * f ;
}

ll t , n , m , k , Res[maxn] , cnt , a[maxn] , rt[maxn] , ans[maxn] ;
char s[maxn] , S[maxn] ;
bool vis[maxn] ;

int main(){
	n = read() ;
	for(int i = 1 ; i <= n ; i ++){
		a[i] = read() ;
		rt[a[i]] = i ;
	}
	map < ll , ll > mp ;
	for(int i = 2 ; i <= n ; i ++){
		mp[__gcd(a[i] , a[i - 1])] ++ ;
	}
	ans[1] = n ;
	for(int i = 2 ; i <= n ; i ++){
		if(rt[i] == 1){
			mp[__gcd(a[rt[i]] , a[rt[i] + 1])] -- ;
			if(mp[i] > 0){
				ans[i] = n ;
			}
			else{
				ans[i] = n - 1 ;
			}
			mp[__gcd(a[rt[i]] , a[rt[i] + 1])] -- ;
			continue ;
		}
		if(rt[i] == n){
			mp[__gcd(a[rt[i]] , a[rt[i] - 1])] -- ;
			if(mp[i] > 0){
				ans[i] = n ;
			}
			else{
				ans[i] = n - 1 ;
			}
			mp[__gcd(a[rt[i]] , a[rt[i] - 1])] ++ ;
			continue ;
		}
		mp[__gcd(a[rt[i]] , a[rt[i] + 1])] -- ;
		mp[__gcd(a[rt[i]] , a[rt[i] - 1])] -- ;
		if(mp[i] > 0){
			ans[i] = n ;
		}
		else{
			ans[i] = n - 1 ;
		}
		mp[__gcd(a[rt[i]] , a[rt[i] + 1])] ++ ;
		mp[__gcd(a[rt[i]] , a[rt[i] - 1])] ++ ;
	}
	for(int i = 1 ; i <= n ; i ++){
		cout << ans[i] << " " ;
	}
	cout << endl ;
	return 0 ;
}