Description

给定一个包含 $n$ 个整数 $a_{1}, \ldots, a_{n}$ 的列表。你可以执行以下操作：选择某个 $a_{i}$ 并将其乘以任意正整数。

你的任务是计算在进行 $k$ 次操作后列表中可能出现的不同整数的最小数量，要求对所有 $0 \le k \le n$ 都进行计算。

Input Format

输入的第一行包含一个整数 $n (1 \le n \le 3 \times 10^{5})$。输入的第二行包含 $n$ 个整数 $a_{i} (1 \le a_{i} \le 10^{6})$。

Output Format

输出一行包含 $n + 1$ 个整数。第 $i$ 个整数应为在进行 $i - 1$ 次操作后列表中可能的不同整数的最小数量。

6
3 4 1 2 1 2

4 4 3 3 2 2 1

Hint

时间限制：3 秒，内存限制：512 MB。

题面翻译由 ChatGPT-4o 提供。