Problem Description

You are given a permutation of length $n$, and an integer $tp\in\{0,1\}$.

One operation is defined as follows:

Choose a subsequence, delete it from the original sequence, and append it to the end of the permutation in the original order.

Please output the minimum number of operations $k$ needed to sort this permutation in increasing order, and also construct a sequence of operations. In particular, if $k\cdot n\geq 3\times 10^6$ or $tp=0$, you do not need to construct it (see the input and output formats).

Definition of a permutation: a permutation of length $n$ is a sequence consisting of positive integers from $1$ to $n$, where each number appears exactly once.

Definition of a subsequence: we say that sequence $b$ is a subsequence of sequence $a$ if and only if $b$ can be obtained by deleting some elements from $a$.

Input Format

The first line contains two integers $n, tp$, representing the permutation length, and whether you need to construct a solution.

The second line contains $n$ numbers. The $i$-th number is the $i$-th element of the permutation $a_i$. It is guaranteed that all these numbers are pairwise distinct.

Output Format

The first line contains one number $k$, representing the minimum number of operations needed.

If $k\cdot n\geq 3\times 10^6$ or $tp=0$, output -1 on the second line and exit.

Otherwise, output the next $k$ lines. In each line, the first number $c$ is the length of the subsequence chosen in this operation. Then output $c$ pairwise distinct numbers, indicating which indices (in the current sequence) are chosen to form the subsequence. The order of these indices can be arbitrary.

4 1
4 3 2 1

2
2 1 3
2 1 3

5 1
5 2 3 4 1

2
3 2 3 4
1 1

5 0
5 2 3 4 1

2
-1

8 0
1 8 5 4 3 2 6 7

3
-1

8 0
1 3 5 7 2 4 6 8

2
-1

Hint

This problem uses bundled testdata.

$\texttt{Subtask 1(1pts)}:$ $a_i=i$.

$\texttt{Subtask 2(19pts):}$ $a_i=n-i+1$.

$\texttt{Subtask 3(15pts):}$ $n\le 5$.

$\texttt{Subtask 4(20pts):}$ $n\le 2\times 10^3$.

$\texttt{Subtask 5(15pts):}$ $tp=0$.

$\texttt{Subtask 6(30pts):}$ no special constraints.

For all data, $1\leq n \leq 10^5$, and it is guaranteed that $a$ is a permutation.

Translated by ChatGPT 5