Стас — воспитатель в детском саду. Под его попечением находятся \(n\) детей. Он решил собрать из некоторых из них команду для «brawl:go 2».
У Стаса есть \(n\) улучшений, \(i\)-е из которых имеет тип \(a_i\). Сила ребенка равняется количеству различных типов улучшений у него.
Если Стас создает команду размера \(k\), он распределит все \(n\) улучшений между \(k\) детьми так, чтобы у каждого из \(k\) детей было хотя бы одно улучшение, и каждое улучшение он выдал ровно одному ребенку.
Для каждого целого \(k\) от \(1\) до \(n\) найдите минимальную сумму сил детей в команде размера \(k\).
Выходные данные
Для каждого набора входных данных выведите \(n\) чисел, где \(k\)-е число это минимальная суммарная сила команды размера \(k\).
Примечание
Для первого набора входных данных можно раздавать улучшения так, чтобы суммарная сила была минимальна:
- \(k = 1: \{1, 1, 2\}\)
- \(k = 2: \{1, 1\}, \{2\}\)
- \(k = 3: \{1\}, \{1\}, \{2\}\)
Для второго набора входных данных можно раздавать улучшения так, чтобы суммарная сила была минимальна:
- \(k = 1: \{1, 2, 2, 2, 4, 5\}\)
- \(k = 2: \{2, 2, 2, 4, 5\}, \{1\}\)
- \(k = 3: \{2, 2, 2, 5\}, \{1\}, \{4\}\)
- \(k = 4: \{2, 2, 2\}, \{1\}, \{4\}, \{5\}\)
- \(k = 5: \{2, 2\}, \{1\}, \{2\}, \{4\}, \{5\}\)
- \(k = 6: \{1\}, \{2\}, \{2\}, \{2\}, \{4\}, \{5\}\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3
1 1 2
6
5 1 2 2 2 4
|
2 2 3
4 4 4 4 5 6
|