C. Пока я срываюсь
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рик и Морти хотят найти мистера PBH, и они не могут сделать это сами. Поэтому они нуждаются в мистерах Мисиксах. Они сгенерировали n мистеров Мисиксов, стоящих в линию и пронумерованных от 1 до n. У каждого из них имеется собственный цвет. i-й мистер Мисикс имеет цвет ai.

Рик и Морти собирают свою армию и хотят разделить мистеров Мисиксов на некоторые отряды. Они не хотят, чтобы отряд был слишком разноцветным, поэтому каждый отряд должен иметь мистеров Мисиксов не более, чем k различных цветов. Также каждый отряд должен быть непрерывным отрезком мистеров Мисиксов на этой линии. Это значит, что для всех 1 ≤ i ≤ e ≤ j ≤ n, если мистер Мисикс номер i и мистер Мисикс номер j в одном и том же отряде, то и мистер Мисикс номер e должен быть в том же отряде.

Также каждый отряд нуждается в собственной крепости, и постройка крепости стоит денег, поэтому они хотят найти минимальное количество отрядов, которое можно получить.

Рик и Морти окончательно не выбрали точное значение k, поэтому для каждого k от 1 до n (включительно) необходимо узнать минимальное количество крепостей.

Входные данные

Первая строка входных данных содержит единственное целое число n (1 ≤ n ≤ 105) — количество мистеров Мисиксов.

Вторая строка входных данных содержит n целых чисел a1, a2, ..., an, разделенных пробелами (1 ≤ ai ≤ n) — цвета мистеров Мисиксов в порядке, в котором они стоят в линию.

Выходные данные

В единственной строке выведите n целых чисел разделенных пробелом. i-е число должно быть равно минимальному количеству крепостей необходимых, если значение k равно i.

Примеры
Входные данные
5
1 3 4 3 3
Выходные данные
4 2 1 1 1
Входные данные
8
1 5 7 8 1 7 6 1
Выходные данные
8 4 3 2 1 1 1 1
Примечание

Для первого тестового примера некоторые оптимальные пути разделения армии на отряды для каждого k:

  1. [1], [3], [4], [3, 3]
  2. [1], [3, 4, 3, 3]
  3. [1, 3, 4, 3, 3]
  4. [1, 3, 4, 3, 3]
  5. [1, 3, 4, 3, 3]

Для второго тестового примера некоторые оптимальные пути разделения армии на отряды для каждого k:

  1. [1], [5], [7], [8], [1], [7], [6], [1]
  2. [1, 5], [7, 8], [1, 7], [6, 1]
  3. [1, 5, 7], [8], [1, 7, 6, 1]
  4. [1, 5, 7, 8], [1, 7, 6, 1]
  5. [1, 5, 7, 8, 1, 7, 6, 1]
  6. [1, 5, 7, 8, 1, 7, 6, 1]
  7. [1, 5, 7, 8, 1, 7, 6, 1]
  8. [1, 5, 7, 8, 1, 7, 6, 1]