P15109 Adverse Present

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$.

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.

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.

**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