D. Сортировка шаров
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть $$$n$$$ разноцветных шаров, расположенных в ряд. Шары покрашены в $$$n$$$ различных цветов, пронумерованных от $$$1$$$ до $$$n$$$. Цвет $$$i$$$-го слева шара равен $$$c_i$$$. Вы хотите переупорядочить шары так, чтобы $$$i$$$-й слева шар имел цвет $$$i$$$. Для этого вы можете использовать $$$k \ge 1$$$ одинаковых шаров цвета $$$0$$$.

Из-за странных свойств шаров их можно переупорядочивать только используя следующие операции:

  1. Поместить шар цвета $$$0$$$ на любую позицию в ряду (между любыми двумя соседними шарами, перед первым шаром или после последнего шара), не меняя порядок остальных шаров. Эту операцию можно использовать не более $$$k$$$ раз, так как у вас есть всего $$$k$$$ шаров цвета $$$0$$$.
  2. Выбрать любой шар ненулевого цвета, такой, что хотя бы один из соседних с ним шаров имеет цвет $$$0$$$, и переместить этот шар (ненулевого цвета) на любую позицию в ряду (между любыми двумя соседними шарами, перед первым шаром или после последнего шара), не меняя порядок остальных шаров. Эту операцию можно использовать сколько угодно раз, но за каждое её использование вы должны заплатить $$$1$$$ монету.

Вы можете применять эти операции в любом порядке. После того, как вы закончите применять операции, все шары цвета $$$0$$$ магическим образом исчезнут из ряда. После этого в ряду останутся только $$$n$$$ шаров ненулевых цветов.

Какое наименьшее количество монет вам нужно потратить на операции второго типа, чтобы после исчезновения всех шаров нулевого цвета $$$i$$$-й слева шар имел цвет $$$i$$$ для всех $$$i$$$ от $$$1$$$ до $$$n$$$? Можно показать, что при данных ограничениях это всегда можно сделать.

Решите задачу для всех $$$k$$$ от $$$1$$$ до $$$n$$$.

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

В первой строке задано целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следуют описания наборов входных данных.

В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 500$$$) — количество шаров в ряду.

Во второй строке заданы $$$n$$$ различных целых чисел $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le n$$$) — цвета шаров в ряду.

Гарантируется, что сумма $$$n$$$ по всем тестам не превышает $$$500$$$.

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

Для каждого набора входных данных выведите $$$n$$$ чисел: $$$i$$$-е ($$$1 \le i \le n$$$) из них должно быть равно наименьшему количеству монет, которого достаточно для требуемого переупорядочивания шаров при $$$k = i$$$.

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

В первом наборе входных данных есть $$$n = 6$$$ шаров. Цвета шаров слева направо равны $$$[\, 2, 3, 1, 4, 6, 5 \,]$$$.

Пусть $$$k = 1$$$. Один из способов переставить шары в требуемом порядке за $$$3$$$ монеты:

$$$[\, 2, 3, 1, 4, 6, 5 \,]$$$ $$$\xrightarrow{\, 1 \,}$$$ $$$[\, 2, 3, 1, 4, \color{red}{0}, 6, 5 \,]$$$ $$$\xrightarrow{\, 2 \,}$$$ $$$[\, 2, 3, \color{blue}{4}, 1, 0, 6, 5 \,]$$$ $$$\xrightarrow{\, 2 \,}$$$ $$$[\, \color{blue}{1}, 2, 3, 4, 0, 6, 5 \,]$$$ $$$\xrightarrow{\, 2\,}$$$ $$$[\, 1, 2, 3, 4, 0, 5, \color{blue}{6} \,]$$$

Число над стрелкой обозначает тип операции. Красным выделены шары, вставленные в операциях первого типа, синим — шары, передвинутые в операциях второго типа.

Можно показать, что для $$$k = 1$$$ невозможно расставить шары в правильном порядке, потратив меньше $$$3$$$ монет.

Пусть $$$k = 2$$$. Один из способов переставить шары в требуемом порядке за $$$2$$$ монеты:

$$$[\, 2, 3, 1, 4, 6, 5 \,]$$$ $$$\xrightarrow{\, 1 \,}$$$ $$$[\, 2, 3, 1, 4, 6, \color{red}{0}, 5\,]$$$ $$$\xrightarrow{\, 2 \,}$$$ $$$[\, 2, 3, 1, 4, 0, 5, \color{blue}{6}\,]$$$ $$$\xrightarrow{\, 1 \,}$$$ $$$[\, 2, 3, \color{red}{0}, 1, 4, 0, 5, 6 \,]$$$ $$$\xrightarrow{\, 2 \,}$$$ $$$[\, \color{blue}{1}, 2, 3, 0, 4, 0, 5, 6\,]$$$

Эта последовательность операций является корректной и для $$$k$$$, больших $$$2$$$.

Можно показать, что для $$$k$$$ от $$$2$$$ до $$$6$$$ невозможно расставить шары в правильном порядке, потратив меньше $$$2$$$ монет.

Во втором запросе шары уже стоят в правильном порядке, поэтому ответы для всех $$$k$$$ равны $$$0$$$.