Вам дается колода из \(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].
Выходные данные
В первой строке выведите \(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\) операций. Если существует несколько способом отсортировать колоду, вы можете вывести любой из них.
Примечание
Пояснение первого примера: Изначальная колода: [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].
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 1 2 4
|
2
3 1 2 1
2 1 3
|
|
2
|
6
6 5 4 3 2 1
|
1
6 1 1 1 1 1 1
|
|
3
|
1
1
|
0
|