Cyclic Shifts Sorting

题意翻译

给定一个有 $n$ 个正整数的数列 $a_1,...,a_n$。你希望将它们排序。但你现在只能执行下面的操作： - 选定一个 $i(1\leq i\leq n-2)$，将 $[a_i,a_{i+1},a_{i+2}]$ 循环移位。也就是说，$a'_i=a_{i+2},a'_{i+1}=a_i,a'_{i+2}=a_{i+1}$。 你需要构造一种用不超过 $n^2$ 次操作将 $a$ 排序的方案，或者判定无解。 单个测试点里有多组测试数据。 保证 数据组数 $\leq 100$，$3\leq n\leq 500,1\leq a_i\leq 500,\sum n\leq 500$。

题目描述

You are given an array $ a $ consisting of $ n $ integers. In one move, you can choose some index $ i $ ( $ 1 \le i \le n - 2 $ ) and shift the segment $ [a_i, a_{i + 1}, a_{i + 2}] $ cyclically to the right (i.e. replace the segment $ [a_i, a_{i + 1}, a_{i + 2}] $ with $ [a_{i + 2}, a_i, a_{i + 1}] $ ). Your task is to sort the initial array by no more than $ n^2 $ such operations or say that it is impossible to do that. You have to answer $ t $ independent test cases.

输入输出格式

输入格式

The first line of the input contains one integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. Then $ t $ test cases follow. The first line of the test case contains one integer $ n $ ( $ 3 \le n \le 500 $ ) — the length of $ a $ . The second line of the test case contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 500 $ ), where $ a_i $ is the $ i $ -th element $ a $ . It is guaranteed that the sum of $ n $ does not exceed $ 500 $ .

输出格式

For each test case, print the answer: -1 on the only line if it is impossible to sort the given array using operations described in the problem statement, or the number of operations $ ans $ on the first line and $ ans $ integers $ idx_1, idx_2, \dots, idx_{ans} $ ( $ 1 \le idx_i \le n - 2 $ ), where $ idx_i $ is the index of left border of the segment for the $ i $ -th operation. You should print indices in order of performing operations.

输入输出样例

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