A13648 | Cyclic Shifts Sorting

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.