Bajtazarはかつて、かなりの数の切手コレクションを持っていました。しかし、彼は若い頃ほど切手に興味がなくなったため、コレクションを若い切手収集家に譲ることにしました。彼はできるだけ公平にこれを行いたいと考えており、あなたの助けを必要としています。

Bajtazarのコレクションは $n$ 枚の切手で構成されており、そのうち $i$ 番目の切手は都市 $a_i$ のものです。便宜上、都市は整数で表されます。Bajtazarは、コレクションを譲るという広告を新聞に掲載する予定です。もし $k$ 人の希望者が現れた場合、彼は各希望者に切手の部分集合をプレゼントしますが、ある条件を守る必要があります。それは、すべての希望者が全く同じマルチセット（多重集合）の切手を受け取らなければならないということです。つまり、任意の2人の希望者について、どの都市の切手であっても、両者がその都市の切手を同数受け取る必要があります。これは、場合によってはBajtazarが1枚も切手を譲らないことを意味するかもしれません。

Bajtazarは、正確に何人の希望者が現れるか分かりません。そのため、1から $n$ までの各 $k$ について、$k$ 人の希望者が現れた場合にBajtazarが譲ることができる切手の最大枚数を求めてください。

入力

入力の1行目には、Bajtazarのコレクションにある切手の枚数を表す整数 $n$ ($1 \le n \le 300\,000$) が与えられます。

入力の2行目には、Bajtazarの切手の出身都市を表す $n$ 個の整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) が与えられます。

出力

1行で、$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のもとに1人の希望者が現れた場合、Bajtazarはすべての切手を譲ることができます。

2人の希望者が現れた場合、Bajtazarはそれぞれに都市1の切手を2枚、都市42の切手を1枚、都市777の切手を1枚、合計8枚の切手を譲ることができます。

4人の希望者が現れた場合、Bajtazarはそれぞれに都市1の切手を1枚譲ることができます。

4人より多くの希望者が現れた場合、Bajtazarは切手を1枚も譲ることができません。