Problem #3427 - ECNU Online Judge

单点时限: 3.0 sec

内存限制: 256 MB

You are given a list of $n$ integers $a_{1}, \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 the minimum number of different integers that could be on the list after $k$ operations for all $0 \leq k \leq n$ .

输入格式

The first line of the input contains single integer $n$ ( $1 \leq n \leq 3 \cdot 10^{5}$ ).

The second line of the input contains $n$ integers $a_{i}$ ( $1 \leq a_{i} \leq 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.

样例

Input

6
3 4 1 2 1 2

Output

4 4 3 3 2 2 1

1 人解决，2 人已尝试。

2 份提交通过，共有 4 份提交。

9.6 EMB 奖励。

创建: 7 年，4 月前.

修改: 7 年，4 月前.

最后提交: 4 年，4 月前.

来源: NEERC 2017

3427. Equal Numbers

输入格式

输出格式

样例

服务

开源

关于我们