Background

PA 2024 2C

Problem Description

This problem is translated from PA 2024 Round 2 Znaczki pocztowe.

Byteasar once collected a large number of postage stamps. However, he is no longer as interested in stamps as he was when he was young, so he decided to give his collection to younger stamp collectors. Still, he wants to do this as fairly as possible, so he needs your help.

Byteasar's collection consists of $n$ stamps, where the $i$-th stamp comes from city $a_i$. For simplicity, we represent cities using integers. Byteasar plans to publish an announcement in a newspaper saying that he intends to give away the stamps from his collection. If there are $k$ people willing to receive them, he will give each person a subset of stamps under the following condition: everyone must receive the same multiset of stamps. This means that for any two applicants and for any city, both applicants must receive the same number of stamps from that city. In particular, this may mean that Byteasar gives away no stamps at all.

Byteasar does not know how many people will show up. Therefore, for each $k$ from $1$ to $n$, you need to determine the maximum number of stamps Byteasar can give away if there are $k$ people willing to receive them.

Input Format

The first line contains an integer $n\ (1\le n\le 300\,000)$, the number of stamps in Byteasar's collection.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n\ (1\le a_i\le 10^9)$, where $a_i$ is the city number of the $i$-th stamp.

Output Format

Output one line with $n$ integers. The $k$-th integer should be the maximum number of stamps Byteasar can give away if there are $k$ people willing to receive his stamps.

9
1 1 777 42 777 1 42 1 777

9 8 6 4 0 0 0 0 0

Hint

If there is one person willing to receive them, Byteasar can give him all the stamps.

If there are two people, Byteasar can give each of them two stamps from city $1$, one stamp from city $42$, and one stamp from city $777$, for a total of $8$ stamps.

If there are four people, Byteasar can give each of them one stamp from city $1$.

If the number of people willing to receive them is greater than four, Byteasar will not be able to give away any stamps.

Translated by ChatGPT 5