CF1650D.Twist the Permutation

Petya got an array $a$ of numbers from $1$ to $n$, where $a[i]=i$.

He performed $n$ operations sequentially. In the end, he received a new state of the $a$ array.

At the $i$-th operation, Petya chose the first $i$ elements of the array and cyclically shifted them to the right an arbitrary number of times (elements with indexes $i+1$ and more remain in their places). One cyclic shift to the right is such a transformation that the array $a=[a_1, a_2, \dots, a_n]$ becomes equal to the array $a = [a_i, a_1, a_2, \dots, a_{i-2}, a_{i-1}, a_{i+1}, a_{i+2}, \dots, a_n]$.

For example, if $a = [5,4,2,1,3]$ and $i=3$ (that is, this is the third operation), then as a result of this operation, he could get any of these three arrays:

• $a = [5,4,2,1,3]$ (makes $0$ cyclic shifts, or any number that is divisible by $3$);
• $a = [2,5,4,1,3]$ (makes $1$ cyclic shift, or any number that has a remainder of $1$ when divided by $3$);
• $a = [4,2,5,1,3]$ (makes $2$ cyclic shifts, or any number that has a remainder of $2$ when divided by $3$).

Let's look at an example. Let $n=6$, i.e. initially $a=[1,2,3,4,5,6]$. A possible scenario is described below.

• $i=1$: no matter how many cyclic shifts Petya makes, the array $a$ does not change.
• $i=2$: let's say Petya decided to make a $1$ cyclic shift, then the array will look like $a = [\textbf{2}, \textbf{1}, 3, 4, 5, 6]$.
• $i=3$: let's say Petya decided to make $1$ cyclic shift, then the array will look like $a = [\textbf{3}, \textbf{2}, \textbf{1}, 4, 5, 6]$.
• $i=4$: let's say Petya decided to make $2$ cyclic shifts, the original array will look like $a = [\textbf{1}, \textbf{4}, \textbf{3}, \textbf{2}, 5, 6]$.
• $i=5$: let's say Petya decided to make $0$ cyclic shifts, then the array won't change.
• $i=6$: let's say Petya decided to make $4$ cyclic shifts, the array will look like $a = [\textbf{3}, \textbf{2}, \textbf{5}, \textbf{6}, \textbf{1}, \textbf{4}]$.

You are given a final array state $a$ after all $n$ operations. Determine if there is a way to perform the operation that produces this result. In this case, if an answer exists, print the numbers of cyclical shifts that occurred during each of the $n$ operations.

佩佳得到了一个由 $1$ 到 $n$ 的数字组成的数组 $a$，其中 $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$ 次循环移动，或任意模 $3$ 余 $1$ 的次数）；
• $a = [4,2,5,1,3]$（执行 $2$ 次循环移动，或任意模 $3$ 余 $2$ 的次数）。

我们来看一个例子。设 $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}]$。

现给出所有 $n$ 次操作后的最终数组状态 $a$。请判断是否存在一种操作序列能产生该结果。若存在，请输出每次操作所执行的循环移动次数（共 $n$ 个整数）。

The first line of the input contains an integer $t$ ($1 \le t \le 500$) — the number of test cases in the test.

The descriptions of the test cases follow.

The first line of the description of each test case contains one integer $n$ ($2 \le n \le 2\cdot10^3$) — the length of the array $a$.

The next line contains the final state of the array $a$: $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) are written. All $a_i$ are distinct.

It is guaranteed that the sum of $n$ values over all test cases does not exceed $2\cdot10^3$.

输入的第一行包含一个整数 $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$。

For each test case, print the answer on a separate line.

Print -1 if the given final value $a$ cannot be obtained by performing an arbitrary number of cyclic shifts on each operation. Otherwise, print $n$ non-negative integers $d_1, d_2, \dots, d_n$ ($d_i \ge 0$), where $d_i$ means that during the $i$-th operation the first $i$ elements of the array were cyclic shifted to the right $d_i$ times.

If there are several possible answers, print the one where the total number of shifts is minimal (that is, the sum of $d_i$ values is the smallest). If there are several such answers, print any of them.

对于每个测试用例，请在单独的一行上输出答案。

如果通过任意次数的循环移位操作均无法得到给定的最终值 $a$，则输出 $-1$。否则，输出 $n$ 个非负整数 $d_1, d_2, \dots, d_n$（其中 $d_i \ge 0$），其中 $d_i$ 表示在第 $i$ 次操作中，将数组的前 $i$ 个元素向右循环移位 $d_i$ 次。

若存在多个可能的答案，请输出总移位次数最少的那个（即所有 $d_i$ 之和最小）。若仍存在多个满足该条件的答案，则输出其中任意一个即可。

The first test case matches the example from the statement.

The second set of input data is simple. Note that the answer $[3, 2, 1]$ also gives the same permutation, but since the total number of shifts $3+2+1$ is greater than $0+0+1$, this answer is not correct.

第一个测试用例与题面中的示例一致。

第二组输入数据较为简单。注意：答案 $[3, 2, 1]$ 同样能生成相同的排列，但由于总移位次数 $3+2+1$ 大于 $0+0+1$，因此该答案不正确。