Cyclic Shifts Sorting
Contest: Codeforces Round 653 (Div. 3)
Difficulty rating: 2400
Tags: brute force, constructive algorithms, implementation, sortings

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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
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

Example output:
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

Editorial:
Firstly, let's solve the easier version of the problem. Assume we are given a permutation, not an array. Notice that the given operation applied to some segment of the permutation cannot change the parity of number of inversions (the number of inversions is the number of such pairs of indices $$$(i, j)$$$ that $$$j > i$$$ and $$$a_j < a_i$$$). So if the number of inversions in the given permutation is odd then we can't sort this permutation (we can't obtain zero inversions).
But if the number of inversions is even then we can always sort the permutation with the following greedy algorithm: let's find the minimum element and move it to the first position. If its position is $$$i$$$ then we can apply the operation to the segment $$$[i-2; i]$$$ and our element will move by two positions to the left. So, after all, our element is either at the first or at the second position. If it's at the second position, let's just apply two additional operations to the segment $$$[1; 3]$$$. Then let's just cut off the first element and solve the problem without it. At the end we have only two numbers that can be not sorted and we can check all three possibilities and choose one which is suitable for us (it's always exists because the number of inversions is even).
How do we solve the problem if we are given the array, not the permutation? First of all, we can prove that if the array contains at least two equal elements, we can always sort it (we will prove it by construction). Let's just renumerate the elements of the given array in a way to obtian the permutation with the even number of inversions. Thus, if $$$a[i_1] \le a[i_2] \le \dots \le a[i_n]$$$ then let's find such a permutation $$$p$$$ that $$$p[i_1] < p[i_2] < \dots < p[i_n]$$$. We can find this permutation easily if we sort the array of pairs $$$(a_i, i)$$$ in increasing order. But there can be one problem: this permutation can have odd number of inversions. Then we need to find two consecutive pairs with the same first values and swap these two elements in the permutation. Because in fact these two numbers are equal in the array and have consecutive values in the permutation, we guaranteed change the parity of number of inversions. Then we can apply our algorithm for permutations and solve the problem for the array. If we failed then the answer is -1. Otherwise the number of operations always does not exceed $$$n^2$$$ (because this sort works like a bubble sort) so our answer is suitable.
Time complexity: $$$O(n^2)$$$.