Postal Stamp Distribution

Byteasar once collected a large number of postage stamps. Now, he wants to give his collection away to young stamp enthusiasts in a fair manner. His collection contains n stamps. The i-th stamp is from city a_i (cities are represented by integers).

Byteasar will publish a notice in the newspaper stating that he intends to distribute his stamps. If exactly k people apply, he will distribute some of his stamps so that each person receives an identical multiset. In other words, for every pair of applicants and for every city, both applicants must receive the same number of stamps from that city. Note that it is also possible that no stamps are distributed at all.

Formally, let the frequency of stamps from a city x be \( f(x) \). When there are k applicants, for each city the maximum number of stamps that can be given out evenly is \(\lfloor f(x)/k\rfloor \cdot k\). Thus, the total maximum number of stamps distributed is:

[ S(k) = \sum_{x} \left(\left\lfloor \frac{f(x)}{k} \right\rfloor \cdot k \right). ]

Your task is to compute, for every integer k between 1 and n (inclusive), the maximum number of stamps Byteasar can distribute if there are k applicants.

inputFormat

The first line contains a single integer n (the number of stamps).

The second line contains n integers \(a_1, a_2, \ldots, a_n\) representing the city each stamp comes from.

outputFormat

Output a single line containing n integers. The k-th integer should be the maximum number of stamps that can be distributed if there are exactly k applicants.

Separate the numbers by a space.

sample

6
1 1 1 2 2 3

6 4 3 0 0 0