D. Перетасовка колоды
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дается колода из $$$n$$$ карт, пронумерованных от $$$1$$$ до $$$n$$$ (в колоде они лежат не обязательно в таком порядке). Вы должны отсортировать колоду, повторив следующую операцию несколько раз.

  • Выберите $$$2 \le k \le n$$$ и разделите колоду на $$$k$$$ непустых последовательных частей $$$D_1, D_2,\dots, D_k$$$ ($$$D_1$$$ содержит первые $$$|D_1|$$$ карт колоды, $$$D_2$$$ содержит следующие $$$|D_2|$$$ карт и т.д.). Затем поставьте эти части в обратном порядке, превратив колоду в $$$D_k, D_{k-1}, \dots, D_2, D_1$$$ (так что первые $$$|D_k|$$$ новой колоды  — $$$D_k$$$, следующие $$$|D_{k-1}|$$$  — $$$D_{k-1}$$$ и т.д.). Внутренний порядок каждой части $$$D_i$$$ не меняется при операции.

Вы должны получить отсортированную колоду (т.е. колоду, где первая карта имеет номер $$$1$$$, вторая  — $$$2$$$ и т.д.), выполнив не более $$$n$$$ операций. Можно доказать, что всегда можно отсортировать колоду, выполнив не более $$$n$$$ операций.

Примеры операций: Ниже приведены три примера корректных операций (на трех колодах разного размера).

  • Если колода имеет вид [3 6 2 1 4 5 7] ($$$3$$$  — первая карта, $$$7$$$  — последняя), мы можем применить операцию с $$$k=4$$$ и $$$D_1=$$$[3 6], $$$D_2=$$$[2 1 4], $$$D_3=$$$[5], $$$D_4=$$$[7]. Таким образом, колода становится [7 5 2 1 4 3 6].
  • Если колода имеет вид [3 1 2], то мы можем применить операцию с $$$k=3$$$ и $$$D_1=$$$[3], $$$D_2=$$$[1], $$$D_3=$$$[2]. При этом колода становится [2 1 3].
  • Если колода имеет вид [5 1 2 4 3 6], то мы можем применить операцию с $$$k=2$$$ и $$$D_1=$$$[5 1], $$$D_2=$$$[2 4 3 6]. При этом колода становится [2 4 3 6 5 1].
Входные данные

Первая строка ввода содержит одно целое число $$$n$$$ ($$$1\le n\le 52$$$)  — количество карт в колоде.

Вторая строка содержит $$$n$$$ целых чисел $$$c_1, c_2, \dots, c_n$$$ – карты в колоде. Первая карта  — $$$c_1$$$, вторая  — $$$c_2$$$, и так далее.

Гарантируется, что для всех $$$i=1,\dots,n$$$ существует ровно одно $$$j\in\{1,\dots,n\}$$$ такое, что $$$c_j = i$$$.

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

В первой строке выведите $$$q$$$  — число операций, которые вы выполните (должно выполняться $$$0\le q\le n$$$).

Затем выведите $$$q$$$ строк, каждая из которых описывает одну операцию.

Чтобы описать операцию, выведите в одной строке $$$k$$$  — число частей, на которые вы собираетесь разделить колоду, а затем $$$k$$$ чисел $$$|D_1|, |D_2|, \dots , |D_k|$$$  — размеры частей.

Должно выполняться $$$2\le k\le n$$$, $$$|D_i|\ge 1$$$ для всех $$$i=1,\dots,k$$$, и $$$|D_1|+|D_2|+\cdots + |D_k| = n$$$.

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

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

Пояснение первого примера: Изначальная колода: [3 1 2 4].

  • Первая операция разделяет колоду как [(3)(1 2)(4)], а затем преобразует ее в [4 1 2 3].
  • Вторая операция разделяет колоду как [(4) (1 2 3)], а затем преобразует ее в [1 2 3 4].
Пояснение второго примера: Изначально колода: [6 5 4 3 2 1].
  • Первая (и единственная) операция разделяет колоду как [(6)(5)(4)(3)(2)(1)], а затем преобразует ее в [1 2 3 4 5 6].