给定一个长度为 $$$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$$$ 操作对应的索引。
示例
输入复制
422 133 2 151 5 4 3 244 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]$$$