Bajtazar a accumulé au fil du temps une impressionnante collection de timbres. Cependant, il ne s'y intéresse plus autant que dans sa jeunesse, c'est pourquoi il a décidé de distribuer sa collection à de jeunes passionnés de philatélie. Il souhaite toutefois le faire de la manière la plus équitable possible, et pour cela, il a besoin de ton aide.

La collection de Bajtazar se compose de $n$ timbres, dont le $i$-ième provient de la ville $a_i$. Pour simplifier, nous désignons les villes par des entiers. Bajtazar a l'intention de publier une annonce dans le journal indiquant qu'il prévoit de distribuer sa collection. Si $k$ personnes se présentent, il offrira à chacune d'elles un sous-ensemble de timbres en respectant une condition précise : chaque personne doit recevoir le même multiensemble de timbres. Cela signifie que pour deux personnes quelconques et pour chaque ville, les deux personnes doivent recevoir le même nombre de timbres provenant de cette ville. Cela peut notamment signifier que Bajtazar ne distribue aucun timbre.

Bajtazar ne sait pas exactement combien de personnes se présenteront. Par conséquent, pour chaque nombre $k$ compris entre $1$ et $n$, tu dois déterminer le nombre maximal de timbres que Bajtazar peut distribuer si $k$ personnes se présentent.

Entrée

La première ligne de l'entrée contient un entier $n$ ($1 \le n \le 300\,000$), représentant le nombre de timbres dans la collection de Bajtazar.

La deuxième ligne de l'entrée contient $n$ entiers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), les numéros des villes d'origine des timbres de Bajtazar.

Sortie

La seule ligne de sortie doit contenir $n$ entiers séparés par des espaces ; le $k$-ième entier doit être égal au nombre maximal de timbres que Bajtazar peut distribuer si $k$ personnes se présentent.

Exemples

Entrée 1

9
1 1 777 42 777 1 42 1 777

Sortie 1

9 8 6 4 0 0 0 0 0

Remarque

Si une seule personne se présente à Bajtazar, il peut lui donner tous ses timbres.

S'il y a deux personnes, Bajtazar peut leur donner à chacune deux timbres de la ville 1, un timbre de la ville 42 et un timbre de la ville 777, soit un total de 8 timbres.

S'il y a quatre personnes, Bajtazar peut leur donner à chacune un timbre de la ville 1.

S'il y a plus de quatre personnes, Bajtazar ne pourra distribuer aucun timbre.