CF1650D Twist the Permutation

Petya 得到了一个长度为 $n$ 的数组 $a$，其中 $a[i]=i$，即数组初始为 $[1,2,\dots,n]$。 他依次进行了 $n$ 次操作。最终，他得到了数组 $a$ 的一个新状态。 在第 $i$ 次操作时，Petya 选择了数组的前 $i$ 个元素，并将它们循环右移任意次数（下标大于 $i$ 的元素保持不变）。一次循环右移指的是将数组 $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$：假设 Petya 进行了 $1$ 次循环右移，则数组变为 $a = [\textbf{2}, \textbf{1}, 3, 4, 5, 6]$。 - $i=3$：假设 Petya 进行了 $1$ 次循环右移，则数组变为 $a = [\textbf{3}, \textbf{2}, \textbf{1}, 4, 5, 6]$。 - $i=4$：假设 Petya 进行了 $2$ 次循环右移，则数组变为 $a = [\textbf{1}, \textbf{4}, \textbf{3}, \textbf{2}, 5, 6]$。 - $i=5$：假设 Petya 进行了 $0$ 次循环右移，则数组不变。 - $i=6$：假设 Petya 进行了 $4$ 次循环右移，则数组变为 $a = [\textbf{3}, \textbf{2}, \textbf{5}, \textbf{6}, \textbf{1}, \textbf{4}]$。 现在给定所有操作完成后的最终数组 $a$，请判断是否存在一种操作方案可以得到该结果。如果存在，请输出每次操作循环右移的次数。 如果有多种方案，输出循环右移总次数最小的那一种（即 $d_1+d_2+\dots+d_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$。

对于每个测试用例，输出一行答案。 如果无法通过上述操作得到给定的最终数组 $a$，输出 $-1$。 否则，输出 $n$ 个非负整数 $d_1, d_2, \dots, d_n$（$d_i \ge 0$），其中 $d_i$ 表示第 $i$ 次操作时，前 $i$ 个元素循环右移了 $d_i$ 次。 如果有多种答案，输出循环右移总次数最小的那一种。如果仍有多种方案，输出任意一种。

第一个测试用例与题目描述中的例子一致。 第二组输入数据较为简单。注意，答案 $[3, 2, 1]$ 也能得到同样的排列，但由于循环右移总次数 $3+2+1$ 大于 $0+0+1$，因此该答案不是正确答案。 由 ChatGPT 4.1 翻译