Bajtazar ha acumulado con el tiempo una impresionante colección de sellos postales. Sin embargo, ya no le interesa tanto como en su juventud, por lo que ha decidido regalar su colección a jóvenes entusiastas de la filatelia. No obstante, le gustaría hacerlo de la manera más justa posible, y para ello necesita tu ayuda.
La colección de Bajtazar consta de $n$ sellos, donde el $i$-ésimo sello proviene de la ciudad $a_i$. Para facilitar el proceso, identificamos las ciudades con números enteros. Bajtazar tiene la intención de publicar un anuncio en el periódico indicando que planea regalar su colección. Si se presentan $k$ interesados, les regalará a cada uno un subconjunto de sellos bajo una condición específica: cada interesado debe recibir el mismo multiconjunto de sellos. Esto significa que, para cada par de interesados y para cada ciudad, ambos deben recibir la misma cantidad de sellos de esa ciudad. En particular, esto puede significar que Bajtazar no regale ningún sello.
Bajtazar no sabe exactamente cuántos interesados se presentarán. Por lo tanto, para cada número $k$ en el rango de $1$ a $n$, debes determinar la cantidad máxima de sellos que Bajtazar puede regalar si se presentan $k$ interesados.
Entrada
La primera línea de la entrada contiene un número entero $n$ ($1 \le n \le 300\,000$), que representa el número de sellos en la colección de Bajtazar.
La segunda línea de la entrada contiene $n$ números enteros $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), los números de las ciudades de donde provienen los sellos de Bajtazar.
Salida
En la única línea de salida debe haber $n$ números separados por espacios simples; el $k$-ésimo número debe ser igual a la cantidad máxima de sellos que Bajtazar puede regalar si se presentan $k$ interesados.
Ejemplos
Entrada 1
9 1 1 777 42 777 1 42 1 777
Salida 1
9 8 6 4 0 0 0 0 0
Nota
Si se presenta un interesado, Bajtazar puede entregarle todos sus sellos.
Si hay dos interesados, Bajtazar puede darles a cada uno dos sellos de la ciudad 1, un sello de la ciudad 42 y un sello de la ciudad 777, es decir, un total de 8 sellos.
Si hay cuatro interesados, Bajtazar puede darles a cada uno un sello de la ciudad 1.
Si hay más de cuatro interesados, Bajtazar no podrá regalar ningún sello.