같은 수 만들기

정수 $n$개로 이루어진 목록 $a_1, a_2, \ldots, a_n$이 주어진다. 한 번의 연산에서 목록의 원소 하나를 골라 임의의 양의 정수를 곱할 수 있다. 곱하는 수로 $1$을 골라도 된다.

$0 \le k \le n$인 모든 $k$에 대해, 연산을 $k$번 수행한 뒤 목록에 남을 수 있는 서로 다른 정수 개수의 최솟값을 구한다.

첫째 줄에 정수 $n$ ($1 \le n \le 3 \times 10^5$)이 주어진다.

둘째 줄에 정수 $a_i$ ($1 \le a_i \le 10^6$) $n$개가 공백으로 구분되어 주어진다.

한 줄에 정수 $n+1$개를 공백으로 구분해 출력한다. $i$번째 정수는 연산을 $i-1$번 수행한 뒤 목록에 남을 수 있는 서로 다른 정수 개수의 최솟값이다.