Bajtazar đã tích lũy được một bộ sưu tập tem bưu chính đáng kể. Tuy nhiên, ông không còn quá quan tâm đến nó như thời còn trẻ, vì vậy ông quyết định tặng lại bộ sưu tập của mình cho những người đam mê sưu tập tem trẻ tuổi hơn. Tuy nhiên, ông muốn thực hiện việc này một cách công bằng nhất có thể và cần sự giúp đỡ của bạn.

Bộ sưu tập của Bajtazar gồm $n$ con tem, trong đó con tem thứ $i$ có nguồn gốc từ thành phố $a_i$. Để thuận tiện, các thành phố được đánh số bằng các số nguyên. Bajtazar dự định đăng một thông báo trên báo rằng ông dự định tặng bộ sưu tập của mình. Nếu có $k$ người đăng ký nhận, ông sẽ tặng cho mỗi người một tập hợp con các con tem với điều kiện sau: mỗi người nhận phải nhận được cùng một đa tập hợp (multiset) các con tem. Điều này có nghĩa là đối với bất kỳ hai người nhận nào và đối với mỗi thành phố, cả hai người đều phải nhận được cùng một số lượng tem từ thành phố đó. Điều này đặc biệt có thể có nghĩa là Bajtazar không tặng con tem nào cả.

Bajtazar không biết chính xác có bao nhiêu người sẽ đăng ký. Do đó, với mỗi số $k$ trong phạm vi từ $1$ đến $n$, bạn cần xác định số lượng tem tối đa mà Bajtazar có thể tặng nếu có $k$ người đăng ký.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên $n$ ($1 \le n \le 300\,000$), biểu thị số lượng tem trong bộ sưu tập của Bajtazar.

Dòng thứ hai của dữ liệu vào chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) – số hiệu các thành phố nơi các con tem của Bajtazar có nguồn gốc.

Dữ liệu ra

Trên một dòng duy nhất, in ra $n$ số nguyên cách nhau bởi dấu cách; số thứ $k$ phải bằng số lượng tem tối đa mà Bajtazar có thể tặng nếu có $k$ người đăng ký.

Ví dụ

Dữ liệu vào 1

9
1 1 777 42 777 1 42 1 777

Dữ liệu ra 1

9 8 6 4 0 0 0 0 0

Ghi chú

Nếu có một người đăng ký, Bajtazar có thể tặng cho người đó tất cả các con tem của mình.

Nếu có hai người đăng ký, Bajtazar có thể tặng cho mỗi người hai con tem từ thành phố 1, một con tem từ thành phố 42 và một con tem từ thành phố 777, tổng cộng là 8 con tem.

Nếu có bốn người đăng ký, Bajtazar có thể tặng cho mỗi người một con tem từ thành phố 1.

Nếu có nhiều hơn bốn người đăng ký, Bajtazar sẽ không thể tặng bất kỳ con tem nào.