Twist the Permutation

题意翻译

你有一个 $1\sim n$ 的排列 $a$，最开始时 $a_i=i$，你可以对这个排列 $a$ 执行 $n$ 次操作，每次指定一个正整数 $x$ ，第 $i$ 次时将 $a_1\sim a_i$ 中的每个数 $a_j$ 变成 $a_{j+x\bmod i}$。 现在告诉你 $n$ 次操作完成后的排列 $a$，请你还原出每轮选择的 $x$ 的值。 数据范围保证：$n\le2\times 10^3$。 翻译提供者：@DaiRuiChen007

题目描述

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.

输入输出样例

输入样例 #1

3
6
3 2 5 6 1 4
3
3 1 2
8
5 8 1 3 2 6 4 7

输出样例 #1

0 1 1 2 0 4 
0 0 1 
0 1 2 0 2 5 6 2

说明

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.