← 返回题目列表

Codeforces · 1374/F

F. 循环移位排序

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

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。

在一次移动中,您可以选择某个索引 $$$i$$$ ($$$1 \le i \le n - 2$$$) 并将段 $$$[a_i, a_{i + 1}, a_{i + 2}]$$$ 循环向右移动(即替换段 $$$[a_i, a_{i + 1}, a_{i + 2}]$$$ 与 $$$[a_{i + 2}, a_i, a_{i + 1}]$$$)。

你的任务是通过不超过$$$n^2$$$这样的操作对初始数组进行排序,或者说这是不可能做到的。

您必须回答 $$$t$$$ 独立测试用例。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 500$$$) — $$$a$$$ 的长度。测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 500$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 个元素 $$$a$$$。

保证$$$n$$$的总和不超过$$$500$$$。

输出

对于每个测试用例,如果无法使用问题陈述中描述的操作对给定数组进行排序,或者第一行的操作数 $$$ans$$$ 和 $$$ans$$$ 整数 $$$idx_1, idx_2, \dots, idx_{ans}$$$ ($$$1 \le idx_i \le n - 2$$$),其中$$$idx_i$$$是第$$$i$$$操作的段左边界索引。您应该按照执行操作的顺序打印索引。

示例

输入 #1

5
5
1 2 3 4 5
5
5 4 3 2 1
8
8 4 5 2 3 6 7 3
7
5 2 1 6 4 7 3
6
1 2 3 3 6 4

输出 #1

0

6
3 1 3 2 2 3 
13
2 1 1 6 4 2 4 3 3 4 4 6 6 
-1
4
3 3 4 4