Description

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$ .

Input Format

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 Format

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.

6
3 4 1 2 1 2

4 4 3 3 2 2 1

Hint

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