← 返回题目列表

Codeforces · 1650/D

D. 扭转排列

中文机器翻译题面 查看原题

Petya 得到了一个从 $$$1$$$ 到 $$$n$$$ 的数组 $$$a$$$,其中 $$$a[i]=i$$$。

他按顺序执行了 $$$n$$$ 操作。最后,他收到了 $$$a$$$ 数组的新状态。

在第 $$$i$$$ 操作中,Petya 选择了数组的前 $$$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$$$:无论 Petya 进行多少次循环移位,数组 $$$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}]$$$。

在所有 $$$n$$$ 操作之后,您将获得最终的数组状态 $$$a$$$。确定是否有办法执行产生此结果的操作。在这种情况下,如果存在答案,则打印每个 $$$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$$$ 次。

如果有多个可能的答案,请打印轮班总数最少的答案(即 $$$d_i$$$ 值的总和最小)。如果有多个这样的答案,请打印其中任何一个。

示例

输入 #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

注意

第一个测试用例与语句中的示例匹配。

第二组输入数据很简单。请注意,答案 $$$[3, 2, 1]$$$ 也给出了相同的排列,但由于移位总数 $$$3+2+1$$$ 大于 $$$0+0+1$$$,因此该答案不正确。