Вам задан массив \(a\), состоящий из \(n\) целых чисел.
За один ход вы можете выбрать некоторый индекс \(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\) независимых наборов тестовых данных.
Выходные данные
Для каждого набора тестовых данных выведите ответ: -1 единственной строкой, если невозможно отсортировать заданный массив, используя операции, описанные в условии задачи, или количество операций \(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
|
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
|