Скоро Codeforces Round 1133 (Div. 1, Div. 2)! Регистрация здесь. ×

F. Whoname и неотсортированный массив
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана перестановка$$$^{\text{∗}}$$$ $$$p$$$ длины $$$n$$$. Над ней можно выполнять следующую операцию любое количество раз (возможно, ноль):

  • Выберите индекс $$$i$$$, где $$$1 \leq i \leq n-1$$$, и перенесите $$$p_i$$$ на место $$$p_1$$$ (сдвигая все элементы между ними вправо), а $$$p_{i+1}$$$ — на место $$$p_n$$$ (сдвигая все элементы между ними влево). Формально, преобразуйте $$$p = [p_1, \ldots, p_n]$$$ в $$$p' = [p_i, p_1, p_2, \ldots, p_{i-1}, p_{i+2}, p_{i+3}, \ldots, p_n, p_{i+1}].$$$

Выведите корректную последовательность операций длины не более $$$4n$$$, чтобы сделать $$$p_i = i$$$ для всех $$$i\,(1 \le i \le n)$$$, или выведите $$$-1$$$, если такой последовательности не существует.

Можно показать, что если корректная последовательность операций существует, то существует и корректная последовательность длины не более $$$4n$$$ операций.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке дано целое число $$$n\,(2 \leq n \leq 5000)$$$ — длина перестановки.

Во второй строке даны $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n \, (1 \le p_i \le n)$$$.

Гарантируется, что $$$p$$$ является перестановкой.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$5000$$$.

Выходные данные

Если корректной последовательности операций не существует, выведите $$$-1$$$.

Иначе в первой строке выведите $$$x\,(0 \leq x \leq 4n)$$$ — количество операций, необходимых для сортировки перестановки. Во второй строке выведите $$$x$$$ целых чисел $$$i_1, \ldots, i_x$$$, где $$$i_j$$$ ($$$1 \leq i_j \leq n-1$$$) обозначает индекс, соответствующий $$$j$$$-й операции.

Пример
Входные данные
4
2
2 1
3
3 2 1
5
1 5 4 3 2
4
4 3 2 1
Выходные данные
-1
3
1 2 1
4
2 2 3 2
3
1 3 1
Примечание

Для первого примера можно показать, что не существует последовательности операций, которая отсортирует перестановку.

Для второго примера одна из корректных последовательностей операций: $$$ [3, 2, 1] \xrightarrow{i_1=1} [3, 1, 2] \xrightarrow{i_2=2} [1, 3, 2] \xrightarrow{i_3=1} [1, 2, 3]. $$$

Для третьего примера одна из корректных последовательностей операций: $$$ [1, 5, 4, 3, 2] \xrightarrow{i_1=2} [5, 1, 3, 2, 4] \xrightarrow{i_2=2} [1, 5, 2, 4, 3] \xrightarrow{i_3=3} [2, 1, 5, 3, 4] \xrightarrow{i_4=2} [1, 2, 3, 4, 5] $$$

Для четвертого примера одна из корректных последовательностей операций: $$$ [4, 3, 2, 1] \xrightarrow{i_1=1} [4, 2, 1, 3] \xrightarrow{i_2=3} [1, 4, 2 ,3] \xrightarrow{i_3=1} [1, 2, 3, 4] $$$