P7023 [NWRRC 2017] Equal Numbers

You are given a list of $n$ integers $a_{1},$ . . . , $a_{n}.$ You can perform the following operation: choose some $a_{i}$ and multiply it by any positive integer. Your task is to compute the minimum number of different integers that could be on the list after $k$ operations for all $0 \le k \le n$ .

The first line of the input contains single integer $n (1 \le n \le 3·10^{5}).$ The second line of the input contains $n$ integers $a_{i} (1 \le a_{i} \le 10^{6}).$

Output a single line that contains $n + 1$ integers. The i-th integer should be the minimum possible number of different integers in the list after $i − 1$ operations.

Time limit: 3 s, Memory limit: 512 MB.