A14915 | 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.

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$ .

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.