Minimizing Distinct Integers after Multiplicative Operations

You are given a list of \(n\) integers \(a_{1},a_{2},\dots,a_{n}\). You can perform the following operation: choose some \(a_{i}\) and multiply it by any positive integer.

Your task is to compute, for every \(k\) with \(0 \le k \le n\), the minimum number of distinct integers that could be present in the list after performing exactly \(k\) operations. In one operation, you may change one element \(a_{i}\) to \(a_{i} \times x\) (with \(x \in \mathbb{Z}^{+}\)). Note that you can only change \(a_{i}\) into a number \(t\) if \(a_{i}\) divides \(t\) (since you must choose \(x = t/a_{i}\) as an integer).

Idea: Think of grouping the numbers. For each distinct number \(d\) in the original list, if it is the smallest (with respect to divisibility) among those that can form a group, it must remain unchanged (a "base group"). For any other distinct number \(d\) that is divisible by some smaller base value, you have the possibility to transform all occurrences of \(d\) into that base value at a cost equal to the frequency of \(d\). By choosing a set of groups appropriately and merging the other groups (if the allowed \(k\) operations cover their frequencies), you can minimize the number of distinct groups in the final list.

inputFormat

The first line contains a single integer \(n\) \( (1 \le n \le 10^5)\), the number of integers in the list.

The second line contains \(n\) space-separated integers \(a_{1},a_{2},\dots,a_{n}\) \( (1 \le a_{i} \le 10^9)\).

outputFormat

Output \(n+1\) space‐separated integers. The \(k\)th integer (with \(k\) from 0 to \(n\)) should be the minimum number of distinct integers that can be obtained after performing exactly \(k\) operations.

sample

3
6 2 3

3 2 2 2