Рик и Морти хотят найти мистера PBH, и они не могут сделать это сами. Поэтому они нуждаются в мистерах Мисиксах. Они сгенерировали n мистеров Мисиксов, стоящих в линию и пронумерованных от 1 до n. У каждого из них имеется собственный цвет. i-й мистер Мисикс имеет цвет ai.
Рик и Морти собирают свою армию и хотят разделить мистеров Мисиксов на некоторые отряды. Они не хотят, чтобы отряд был слишком разноцветным, поэтому каждый отряд должен иметь мистеров Мисиксов не более, чем k различных цветов. Также каждый отряд должен быть непрерывным отрезком мистеров Мисиксов на этой линии. Это значит, что для всех 1 ≤ i ≤ e ≤ j ≤ n, если мистер Мисикс номер i и мистер Мисикс номер j в одном и том же отряде, то и мистер Мисикс номер e должен быть в том же отряде.
Также каждый отряд нуждается в собственной крепости, и постройка крепости стоит денег, поэтому они хотят найти минимальное количество отрядов, которое можно получить.
Рик и Морти окончательно не выбрали точное значение k, поэтому для каждого k от 1 до n (включительно) необходимо узнать минимальное количество крепостей.
Примечание
Для первого тестового примера некоторые оптимальные пути разделения армии на отряды для каждого k:
- [1], [3], [4], [3, 3]
- [1], [3, 4, 3, 3]
- [1, 3, 4, 3, 3]
- [1, 3, 4, 3, 3]
- [1, 3, 4, 3, 3]
Для второго тестового примера некоторые оптимальные пути разделения армии на отряды для каждого k:
- [1], [5], [7], [8], [1], [7], [6], [1]
- [1, 5], [7, 8], [1, 7], [6, 1]
- [1, 5, 7], [8], [1, 7, 6, 1]
- [1, 5, 7, 8], [1, 7, 6, 1]
- [1, 5, 7, 8, 1, 7, 6, 1]
- [1, 5, 7, 8, 1, 7, 6, 1]
- [1, 5, 7, 8, 1, 7, 6, 1]
- [1, 5, 7, 8, 1, 7, 6, 1]