It is not so well known that in his free time, Mr.
Malnar cotributes to the
community by volunteering. That’s right! He is quite active at the volunteering
center for informatics problems.
Recently, he got a call from the center and, as it turns out, there is a shortage of
increasing sequences. Mr. Malnar, who is always willing to help, responded readily.
Namely, he keeps an array of \(n\) integers for this very purpose. All of the integers
from 1 to \(n\) appear exactly once in his array.
Mr. Malnar will select a few increasing subsequences from his array, which he will
donate to the center, and he will keep the rest of the numbers for some other time. It must be noted that
each number from the array can be used for at most one subsequence, that is, the selected subsequences
have distinct indices.
A subsequence is defined as any sequence obtained from the array by deleting some (maybe none) of the
elements, while preserving the order of the remaining elements. A subsequence is said to be increasing if
every number in the subsequence (except for the first one) is larger than the previous one.
Because Mr. Malnar is very generous, he wants all of the sequences he donates to be longest increasing
subsequences. In other words, if \(l\) is the length of the longest increasing subsequence of the staring array,
Mr. Malnar will select a couple of disjoint increasing subsequences, each of length \(l\).
Mr. Malnar wants to donate as many subsequences as possible. For a given array of Mr. Malnar, print
the maximum number of subsequences which comprise his selection and provide an example of such a
selection.

Subtask 1 (10 points): \(1 \le n \le 15\)

Subtask 2 (40 points): \(1 \le n \le 1000\)

Subtask 4 (60 points): \(1 \le n \le 1\,000\,000\)

The first line contains the integer \(n - th\)e size of the array.
The second line contains \(n\) numbers \(p@@RISE_MATH_BLOCK_0@@i \le n\)) which represent the elements of the array. Each
positive integer \(j\) between 1 and \(n\) appears exactly once in the array.

In the first line, print the largest possible number of subsequences in Mr. Malnar’s selection, as well as
the length of the longest increasing subsequence.
In each of the following lines print one of the subsequences from such a selection. A subsequence is defined
by a list of position, i.e. indices of the array, which should be sorted in increasing order.
The printed subsequences should be increasing, disjoint and have the same leng\(th - th\)e length of the
longest increasing subsequence.
The relative order of the subsequences does not matter. Also, if there is more than one solution, you can
print any.

생성자가 기록되지 않았습니다.

출처 COCI 2021/2022 Contest 1