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

У Пети изначально был массив $$$a$$$ целых чисел от $$$1$$$ до $$$n$$$, где $$$a[i]=i$$$.

Он последовательно произвёл $$$n$$$ операций. В итоге он получил новое состояние массива $$$a$$$.

На $$$i$$$-й операции Петя выбирал первые $$$i$$$ элементов массива и произвольное количество раз совершал их циклический сдвиг вправо (элементы с номерами $$$i+1$$$ и больше оставались на своих местах). Один циклический сдвиг вправо — это такое преобразование, что массив $$$a=[a_1, a_2, \dots, a_n]$$$ станет равен $$$a = [a_i, a_1, a_2, \dots, a_{i-2}, a_{i-1}, a_{i+1}, a_{i+2}, \dots, a_n]$$$.

Например, если $$$a = [5,4,2,1,3]$$$ и $$$i=3$$$ (то есть это третья операция), то в результате этой операции он мог получить любой из трёх массивов:

  • $$$a = [5,4,2,1,3]$$$ (делает $$$0$$$ циклических сдвигов или любое количество, которое делится на $$$3$$$);
  • $$$a = [2,5,4,1,3]$$$ (делает $$$1$$$ циклический сдвиг или любое количество, которое имеет остаток $$$1$$$ при делении на $$$3$$$);
  • $$$a = [4,2,5,1,3]$$$ (делает $$$2$$$ циклических сдвига или любое количество, которое имеет остаток $$$2$$$ при делении на $$$3$$$).

Рассмотрим пример. Пусть $$$n=6$$$, то есть изначально $$$a=[1,2,3,4,5,6]$$$. Возможный вариант развития событий описан ниже.

  • $$$i=1$$$: сколько бы циклических сдвигов Петя не производил, массив $$$a$$$ не изменится.
  • $$$i=2$$$: допустим Петя решил сделать $$$1$$$ циклический сдвиг, тогда массив примет вид $$$a = [\textbf{2}, \textbf{1}, 3, 4, 5, 6]$$$.
  • $$$i=3$$$: допустим Петя решил сделать $$$1$$$ циклический сдвиг, тогда массив примет вид $$$a = [\textbf{3}, \textbf{2}, \textbf{1}, 4, 5, 6]$$$.
  • $$$i=4$$$: допустим Петя решил сделать $$$2$$$ циклических сдвига, тогда массив примет вид $$$a = [\textbf{1}, \textbf{4}, \textbf{3}, \textbf{2}, 5, 6]$$$.
  • $$$i=5$$$: допустим Петя решил сделать $$$0$$$ циклических сдвигов, тогда массив не изменится.
  • $$$i=6$$$: допустим Петя решил сделать $$$4$$$ циклических сдвига, тогда массив примет вид $$$a = [\textbf{3}, \textbf{2}, \textbf{5}, \textbf{6}, \textbf{1}, \textbf{4}]$$$.

Вам задано финальное состояние массива $$$a$$$ после всех $$$n$$$ операций. Определите, существует ли способ выполнения операций, который приведёт к этому результату. В случае положительного ответа найдите количество циклических сдвигов, которое могло быть сделано во время каждой из $$$n$$$ операций.

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

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

Далее следуют описания наборов входных данных.

Первая строка описания каждого набора содержит одно целое число $$$n$$$ ($$$2 \le n \le 2\cdot10^3$$$) — длина массива $$$a$$$.

В следующей строке задано финальное состояние массива $$$a$$$: записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$). Все $$$a_i$$$ — различны.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных теста не превосходит $$$2\cdot10^3$$$.

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

Для каждого набора входных данных выведите ответ на отдельной строке.

Выведите -1, если заданное финальное значение $$$a$$$ нельзя получить, производя произвольное количество циклических сдвигов на каждой операции. Иначе выведите $$$n$$$ неотрицательных целых чисел $$$d_1, d_2, \dots, d_n$$$ ($$$d_i \ge 0$$$), где $$$d_i$$$ обозначает, что во время $$$i$$$-й операции первые $$$i$$$ элементов массива были циклически сдвинуты вправо $$$d_i$$$ раз.

Если возможных ответов несколько выведите тот, где суммарное количество сдвигов минимально (то есть сумма значений $$$d_i$$$ наименьшая). Если таких ответов несколько, то выведите любой из них.

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

Первый набор входных данных совпадает с примером из условия.

Второй набор входных данных как видно несложный. Заметим, что ответ $$$[3, 2, 1]$$$ также даёт ту же перестановку, но так как суммарное количество сдвигов $$$3+2+1$$$ больше $$$0+0+1$$$, то такой ответ не является правильным.