Bajtazar 曾经收集了大量的邮票。但他现在对集邮的兴趣不如年轻时那么浓厚了，因此他决定将自己的收藏赠送给年轻的集邮爱好者。他希望尽可能公平地分配这些邮票，并需要你的帮助。

Bajtazar 的收藏由 $n$ 枚邮票组成，其中第 $i$ 枚邮票来自城市 $a_i$。为了方便起见，我们用整数来标记城市。Bajtazar 打算在报纸上刊登一则广告，宣布他计划赠送自己的收藏。如果有 $k$ 名爱好者前来领取，他将赠送给每人一个邮票子集，并满足以下条件：每位爱好者必须收到相同的邮票多重集。这意味着对于任意两名爱好者和任意城市，两人从该城市收到的邮票数量必须相同。这在特殊情况下可能意味着 Bajtazar 一枚邮票也不赠送。

Bajtazar 不知道具体会有多少人前来领取。因此，对于 $1$ 到 $n$ 之间的每一个 $k$，你需要确定如果有 $k$ 名爱好者前来领取，Bajtazar 最多能赠送出多少枚邮票。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 300\,000$)，表示 Bajtazar 收藏的邮票数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)，表示 Bajtazar 的邮票分别来自哪些城市。

输出格式

输出一行，包含 $n$ 个由空格分隔的整数；其中第 $k$ 个数表示如果有 $k$ 名爱好者前来领取，Bajtazar 最多能赠送的邮票总数。

样例

输入 1

9
1 1 777 42 777 1 42 1 777

输出 1

9 8 6 4 0 0 0 0 0

说明

如果有一名爱好者前来，Bajtazar 可以将所有邮票赠送给他。

如果有两名爱好者，Bajtazar 可以给每人两枚来自城市 $1$ 的邮票、一枚来自城市 $42$ 的邮票和一枚来自城市 $777$ 的邮票，总共赠送 $8$ 枚邮票。

如果有四名爱好者，Bajtazar 可以给每人一枚来自城市 $1$ 的邮票。

如果有超过四名爱好者，Bajtazar 将无法赠送任何邮票。