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 將無法贈送任何郵票。