Equal Numbers

Time limit3sMemory limit512 MB

Summary

For each k from 0 to n, find the fewest distinct values possible after multiplying k list elements by positive integers.

Level: Medium7 of 10
Topics: Number theory, Greedy, Sorting, Math
Solved: No attempts yet

Problem

You are given a list of $n$ integers $a_1, a_2, \ldots, a_n$ . In one operation you choose one element of the list and multiply it by any positive integer. The multiplier can be $1$ .

For every $k$ with $0 \le k \le n$ , compute the minimum number of different integers the list can contain after $k$ operations.

Input

The first line contains one integer $n$ ( $1 \le n \le 3 \times 10^5$ ).

The second line contains $n$ integers $a_i$ ( $1 \le a_i \le 10^6$ ), separated by spaces.

Output

Print $n+1$ integers on one line, separated by spaces. The $i$ -th integer is the minimum number of different integers the list can contain after $i-1$ operations.

Examples3

Example 1
Input
```
6
3 4 1 2 1 2
```
Expected output
```
4 4 3 3 2 2 1
```
Example 2
Input
```
1
1
```
Expected output
```
1 1
```
Example 3
Input
```
5
7 7 7 7 7
```
Expected output
```
1 1 1 1 1 1
```