Я на пике продуктивности, и это глубоко.
Вам даны две перестановки\(^{\text{∗}}\) \(a\) и \(b\), обе длины \(n\).
Вы можете выполнить следующую трехшаговую операцию над перестановкой \(a\):
- Выбрать индекс \(i\) (\(1 \le i \le n\)).
- Циклически сдвинуть \(a_1, a_2, \ldots, a_{i-1}\) на \(1\) вправо. Если вы выбрали \(i = 1\), то этот диапазон не существует, и вам не надо его сдвигать.
- Циклически сдвинуть \(a_{i + 1}, a_{i + 2}, \ldots, a_n\) на \(1\) вправо. Если вы выбрали \(i = n\), то этот диапазон не существует, и вам не надо его сдвигать.
После операции массив \(a_1,a_2,\ldots, a_{i-2},a_{i-1},a_i,a_{i + 1}, a_{i + 2},\ldots,a_{n-1}, a_n\) преобразуется в \(a_{i-1},a_1,\ldots,a_{i-3},a_{i-2},a_i,a_n, a_{i + 1},\ldots,a_{n-2}, a_{n-1}\).
Вот несколько примеров операций, выполняемых над тождественной перестановкой \([1,2,3,4,5,6,7]\) длины \(7\):
- Если мы выберем \(i = 3\), то она станет \([2, 1, 3, 7, 4, 5, 6]\).
- Если мы выберем \(i = 1\), то это станет \([1, 7, 2, 3, 4, 5, 6]\).
- Если мы выберем \(i = 7\), то это станет \([6, 1, 2, 3, 4, 5, 7]\).
Заметим, что позиция
\(i\) не сдвигается.
Найдите конструкцию, использующую не более \(2n\) операций, чтобы \(a\) стала равна \(b\), или выведите \(-1\), если это невозможно. Количество операций не обязательно должно быть минимальным. Можно показать, что если возможно сделать \(a\) равным \(b\), то это можно сделать не более чем за \(2n\) операций.
Выходные данные
Для каждого набора входных данных:
Если существует последовательность операций для преобразования \(a\) в \(b\), выведите одно целое число \(q\) (\(0\le q\le 2n\)) — количество операций, в первой строке, и \(q\) целых чисел, где \(i\)-е число представляет индекс на \(i\)-й операции, во второй строке.
Если последовательность операций не существует, то в единственной строке выведите \(-1\).
Примечание
В первом наборе входных данных вы можете не совершать операции, так как \(a=b\).
Во втором наборе входных данных можно доказать, что \(a\) не может быть преобразовано в \(b\).
В третьем наборе входных данных \(a\) преобразуется в \([2,3,1]\) после первой операции и в \(b\) после второй операции.