Migrated from Lutece 2024 小埋酱的游戏

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

小埋酱又买了新游戏啦！我们手里有 $n$ 个数字，你花费一个金币，就可以选择一个数字 $a_i$ 释放神奇的魔法将这个数字乘以一个大于 $0$ 的常数。 小埋酱想要知道，如果她手中有 $x$ 个金币，那么她可以获得的，不同数字的数量最小值是多少呢？

Input

第一行一个数字 $n$（0<n<=3e5），第二行 $n$ 个数字 $a_i$ (1<=a<=1e6)表示小埋酱手里的第 $i$ 个数字

Output

输出一行包括 $n+1$ 个数字 第 $i$ 个数字表示小埋酱手中有 $i-1$ 个金币时可以获得的不同数字的数量最小值

Samples

6
3 4 1 2 1 2

4 4 3 3 2 2 1

Resources

每周一题div1