У вас есть перестановка — массив \(a = [a_1, a_2, \ldots, a_n]\) из различных целых чисел от \(1\) до \(n\). Длина перестановки \(n\) нечётна.
Вам нужно отсортировать её по возрастанию.
За один шаг вы можете выбрать любой префикс перестановки, имеющий нечётную длину, и перевернуть его. Формально, если \(a = [a_1, a_2, \ldots, a_n]\), вы можете выбрать любое нечётное целое число \(p\) от \(1\) до \(n\) включительно и сделать \(a\) равной \([a_p, a_{p-1}, \ldots, a_1, a_{p+1}, a_{p+2}, \ldots, a_n]\).
Найдите способ отсортировать перестановку \(a\), используя не более \(\frac{5n}{2}\) переворотов такого рода, или определите, что такого способа не существует. Минимизировать число переворотов не нужно.
Выходные данные
Для каждого набора входных данных, если невозможно отсортировать заданную перестановку, используя не более \(\frac{5n}{2}\) шагов, выведите одно целое число \(-1\).
В противном случае выведите целое число \(m\) (\(0 \le m \le \frac{5n}{2}\)) — число переворотов в вашей последовательности шагов, и \(m\) целых чисел \(p_i\) (\(1 \le p_i \le n\); \(p_i\) нечётно) — длины префиксов \(a\), которые нужно перевернуть, в хронологическом порядке.
Обратите внимание, что \(m\) минимизировать не нужно. Если существует несколько решений, выведите любое из них.
Примечание
В первом наборе входных данных перестановка уже отсортирована. Любое чётное число переворотов префикса длины \(3\) не влияет на этот факт.
Во втором наборе входных данных после переворота префикса длины \(3\) перестановка станет равна \([5, 4, 3, 2, 1]\), и далее после переворота префикса длины \(5\) перестановка станет равна \([1, 2, 3, 4, 5]\).
В третьем наборе входных данных перестановку отсортировать невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
1 2 3
5
3 4 5 2 1
3
2 1 3
|
4
3 3 3 3
2
3 5
-1
|