eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Розкладання перестановок

Розкладання перестановок

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

У цій задачі перестановкою з n елементів будемо називати послідовність цілих чисел довжини n, у якій кожне число від 0 до n-1 зустрічається рівно один раз. Позначимо i-ий елемент перестановки p як p_i, де i - індекс від 0 до n-1. Визначимо добуток двох перестановок з n елементів a та b як перестановку c з n елементів, таку, що c_i = a_bi_{ }(відмітимо, що операція добутку перестановок лвво-асоцвативна, тобто операції виконуються зліва направо).

Серед перестановок виділимо клас "подвійних" перестановок. Подвійні перестановки - це перестановки, які можуть бути подані у вигляді об'єднання двох зростаючих послідовностей, які не перетинаються. Наприклад, перестановка (1, 3, 4, 0, 5, 2) є подвійною, так як її можна розбити на дві зростаючі послідовності (1, 3, 4, 5) та (0, 2), а перестановка (5, 1, 3, 4, 0, 2) не є подвійною.

Необхідно написати програму, яка розкладає задану перестановку у добуток плдвійних перестановок. При цьому кількість подвійних перестановок у добутку повтнна бути достатньо малою. Ваша програма повинна знаходити розв'язок, який складається не більше, ніж з 15 подвійних перестановок.

Вхідні дані

У першому рядку міститься число n (2n20000).

У другому рядку записано n чисел, які задають собою початкову перестановку.

Вихідні дані

Якщо розв'язок при заданих обмеженнях знайти неможливо, виведіть єдине число -1.

Якщо розв'язок існує, у перший рядок виведіть число k - кількість подвійних перестановок у знайденому розв'язку, а у наступних k рядках виведіть самі подвійні перестановки у порядку їх слудування у добутку.

Приклад

Вхідні дані #1
26
11 20 5 14 21 9 4 12 3 22 15 13 25 16 10 18 6 8 23 17 2 0 24 7 19 1
Вихідні дані #1
5
3 4 5 9 10 11 12 13 14 15 16 18 20 21 22 25 0 1 2 6 7 8 17 19 23 24
1 2 3 5 6 8 12 13 0 4 7 9 10 11 14 15 16 18 19 20 21 22 24 25 17 23
1 3 5 6 0 2 4 7 8 10 11 14 9 12 13 15 18 20 21 22 16 17 19 23 24 25
1 3 0 2 5 7 4 6 8 11 9 10 13 15 12 14 16 17 18 19 20 21 22 23 24 25
0 1 2 3 5 4 6 7 8 9 11 10 13 12 14 15 16 17 19 18 21 20 23 22 25 24
Автор Mike Mirzayanov, Igor Kulkin
Джерело Saratov SU Contest, Thursday, Petrozavodsk Summer Session, August 24, 2006