Twist the Permutation
Contest: Codeforces Round 776 (Div. 3)
Difficulty rating: 1300
Tags: brute force, constructive algorithms, implementation, math

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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
3
6
3 2 5 6 1 4
3
3 1 2
8
5 8 1 3 2 6 4 7

Example output:
0 1 1 2 0 4 
0 0 1 
0 1 2 0 2 5 6 2

Editorial:
The first thing to notice — the answer always exists. For $$$n$$$ numbers $$$1\cdot2\cdot3 \dots n = n!$$$ answer choices, as well as $$$n!$$$ permutation combinations. It remains only to restore the answer from this permutation.
We will restore by performing reverse operations. On the $$$i$$$-th ($$$i = n,~n - 1, ~\dots, ~2, ~1$$$) operation will be selectd the first $$$i$$$ elements of the array and rotate them $$$d[i]$$$ times to the left ( elements with numbers $$$i+1$$$ and more remain in their places).
Where $$$d[i]$$$ is equal to $$$0$$$ if $$$i = 1$$$, otherwise $$$d[i] = (index + 1) \bmod i$$$, and $$$index$$$ – is the index of the number $$$i$$$.
Thus, for each $$$i$$$ from right to left, performing a left cyclic shift operation, we move the number $$$i$$$ at index $$$i$$$.
As a result, we move $$$O(n)$$$ numbers $$$n$$$ times. The time complexity $$$O(n^2)$$$.