Разложение перестановок
В этой задаче перестановкой из 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 (2 ≤ n ≤ 20000).
Во второй строке записаны n чисел, представляющих собой исходную перестановку.
Выходные данные
Если решение при данных ограничениях найти невозможно, выведите единственное число -1.
Если решение существует, в первую строку выведите число k - количество двойных перестановок в найденном решении, а в следующих k строках выведите сами двойные перестановки в порядке их следования в произведении.