← 返回题目列表

Codeforces · 1558/C

C. 底层反转

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

你有一个排列:一个数组 $$$a = [a_1, a_2, \ldots, a_n]$$$,由从 $$$1$$$ 到 $$$n$$$ 的不同整数组成。排列 $$$n$$$ 的长度是奇数。

您需要按升序对排列进行排序。

在一步中,您可以选择具有奇数长度的排列的任何前缀并将其反转。形式上,如果 $$$a = [a_1, a_2, \ldots, a_n]$$$,则可以选择 $$$1$$$ 和 $$$n$$$(含)之间的任何奇数整数 $$$p$$$,并将 $$$a$$$ 设置为 $$$[a_p, a_{p-1}, \ldots, a_1, a_{p+1}, a_{p+2}, \ldots, a_n]$$$。

找到一种使用不超过上述类型的 $$$\frac{5n}{2}$$$ 反转对 $$$a$$$ 进行排序的方法,或者确定这种方法不存在。不必最小化反转次数。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 2021$$$;$$$n$$$ 为奇数)——排列的长度。

第二行包含 $$$n$$$ 不同的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) - 排列本身。

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

输出

对于每个测试用例,如果无法在最多 $$$\frac{5n}{2}$$$ 反转中对给定排列进行排序,则打印单个整数 $$$-1$$$。

否则,打印一个整数 $$$m$$$ ($$$0 \le m \le \frac{5n}{2}$$$),表示步骤序列中的反转次数,后跟 $$$m$$$ 整数 $$$p_i$$$ ($$$1 \le p_i \le n$$$;$$$p_i$$$ 为奇数),表示长度要反转的 $$$a$$$ 的前缀,按时间顺序排列。

请注意,$$$m$$$ 不必最小化。如果有多个答案,请打印其中一个。

示例

输入 #1

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

输出 #1

4
3 3 3 3
2
3 5
-1

注意

在第一个测试用例中,排列已经排序。长度 $$$3$$$ 前缀的任何偶数次反转都不会改变这一事实。

在第二个测试用例中,在反转长度 $$$3$$$ 的前缀后,排列将更改为 $$$[5, 4, 3, 2, 1]$$$,然后在反转长度 $$$5$$$ 的前缀后,排列将更改为 $$$[1, 2, 3, 4, 5]$$$。

在第三个测试用例中,无法对排列进行排序。