← 返回题目列表

Codeforces · 2246/F

F. Whoname 和未排序数组

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

给定一个长度为 $$$n$$$ 的排列$$$^{\text{∗}}$$$ $$$p$$$,您可以对其执行以下操作任意次数(可能为零):

  • 选择索引 $$$i$$$,其中 $$$1 \leq i \leq n-1$$$,并将 $$$p_i$$$ 移动到 $$$p_1$$$ (将中间的所有内容向右移动),并将 $$$p_{i+1}$$$ 移动到 $$$p_n$$$ (将之间的所有内容向左移动)。正式地,您可以将 $$$p = [p_1, \ldots, p_n]$$$ 转换为 $$$p' = [p_i, p_1, p_2, \ldots, p_{i-1}, p_{i+2}, p_{i+3}, \ldots, p_n, p_{i+1}]。$$$

提供长度最多 $$$4n$$$ 的有效操作序列,以使 $$$p_i = i$$$ 对于所有 $$$i\,(1 \le i \le n)$$$,或者如果不存在序列则打印 $$$-1$$$。

可以证明,如果存在有效的操作序列,则存在长度至多$$$4n$$$操作的有效序列。

$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。

第一行包含一个整数 $$$n\,(2 \leq n \leq 5000)$$$ — 排列的长度。

第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n \, (1 \le p_i \le n)$$$。

保证 $$$p$$$ 是一个排列。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$。

输出

如果不存在有效的操作序列,则输出$$$-1$$$。

否则,在第一行输出 $$$x\,(0 \leq x \leq 4n)$$$,即排列排序所需的操作数。第二行,输出 $$$x$$$ 整数 $$$i_1, \ldots, i_x$$$ 其中 $$$i_j$$$ ($$$1 \leq i_j \leq n-1$$$) 表示第 $$$j$$$ 操作对应的索引。

示例

输入
复制

4
2
2 1
3
3 2 1
5
1 5 4 3 2
4
4 3 2 1

输出
复制

-1
3
1 2 1
4
2 2 3 2
3
1 3 1

注意

对于第一个示例,可以证明没有操作序列可以对排列进行排序。

对于第二个示例,一个有效的操作序列是 $$$[3, 2, 1] \xrightarrow{i_1=1} [3, 1, 2] \xrightarrow{i_2=2} [1, 3, 2] \xrightarrow{i_3=1} [1, 2, 3].$$$

对于第三个示例,一个有效的操作序列是 $$$[1, 5, 4, 3, 2] \xrightarrow{i_1=2} [5, 1, 3, 2, 4] \xrightarrow{i_2=2} [1, 5, 2, 4, 3] \xrightarrow{i_3=3} [2, 1, 5, 3, 4] \xrightarrow{i_4=2} [1, 2, 3, 4, 5]$$$

对于第四个示例,一个有效的操作序列是 $$$[4, 3, 2, 1] \xrightarrow{i_1=1} [4, 2, 1, 3] \xrightarrow{i_2=3} [1, 4, 2 ,3] \xrightarrow{i_3=1} [1, 2, 3, 4]$$$