Байтазар в своё время собрал внушительную коллекцию почтовых марок. Однако сейчас он интересуется ими не так сильно, как в молодости, поэтому решил раздать свою коллекцию юным любителям филателии. Он хотел бы сделать это как можно более справедливо, для чего ему нужна твоя помощь.
Коллекция Байтазара состоит из $n$ марок, причём $i$-я марка происходит из города $a_i$. Для удобства города обозначены целыми числами. Байтазар собирается дать в газету объявление о том, что планирует раздать свою коллекцию. Если к нему обратится $k$ желающих, то каждому из них он подарит какой-то поднабор марок с соблюдением определённого условия: каждый желающий должен получить одинаковый мультинабор марок. Это означает, что для любых двух желающих и для каждого города оба желающих должны получить одинаковое количество марок из этого города. В частности, это может означать, что Байтазар не раздаст ни одной марки.
Байтазар не знает, сколько именно желающих к нему обратится. В связи с этим для каждого числа $k$ в диапазоне от $1$ до $n$ ты должен определить, какое максимальное количество марок может раздать Байтазар, если к нему обратится $k$ желающих.
Входные данные
В первой строке входных данных находится одно целое число $n$ ($1 \le n \le 300\,000$), обозначающее количество марок в коллекции Байтазара.
Во второй строке входных данных находятся $n$ целых чисел $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — номера городов, из которых происходят соответствующие марки Байтазара.
Выходные данные
В единственной строке вывода должны находиться $n$ чисел, разделённых одиночными пробелами; $k$-е из них должно быть равно максимальному количеству марок, которые может раздать Байтазар, если к нему обратится $k$ желающих.
Примеры
Пример 1
9 1 1 777 42 777 1 42 1 777
9 8 6 4 0 0 0 0 0
Примечание
Если к Байтазару обратится один желающий, то Байтазар может отдать ему все свои марки.
Если будет два желающих, то Байтазар может дать им по две марки из города 1, по одной марке из города 42 и по одной марке из города 777, то есть в сумме 8 марок.
Если будет четыре желающих, то Байтазар может дать им по одной марке из города 1.
Если будет больше четырёх желающих, то Байтазар не сможет раздать никаких марок.