P7931 [COCI 2021/2022 #1] Volontiranje

Given a permutation $p$ of $1 \sim n$, please take as many pairwise disjoint increasing subsequences as possible, where each subsequence has length equal to the LIS length of the original permutation, and construct one valid solution.

The first line contains an integer $n$. The next line contains $n$ integers $p_i$.

On the first line, output the number of increasing subsequences you choose and their length. On the next several lines, output several integers per line, representing the indices of the elements in one increasing subsequence. You may output the increasing subsequences in any order.

#### Constraints For all testdata, $1 \le n \le 10^6$, $1 \le p_i \le n$. | Subtask | Constraints | Score | | :-----: | :---------: | :---: | | $1$ | $n \le 15$ | $10$ | | $2$ | $n \le 10^3$ | $40$ | | $3$ | No additional constraints | $60$ | #### Notes **The total score for this problem is $110$ points.** This problem is translated from [Croatian Open Competition in Informatics 2021/2022](https://hsin.hr/coci/archive/2021_2022) [Contest #1](https://hsin.hr/coci/archive/2021_2022/contest1_tasks.pdf) T5 Volontiranje. A checker.cpp is provided in the additional files. Translated by ChatGPT 5