It is not so well known that in his free time, Mr. Malnar contributes 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
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
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.
Constraints
In every subtask, it holds that
Subtask | Points | Constraints |
---|---|---|
1 | 10 | |
2 | 40 | |
3 | 60 | No additional constraints. |
Input Specification
The first line contains the integer
The second line contains
Output Specification
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 positions, i.e. indices of the array, which should be sorted in increasing order.
The printed subsequences should be increasing, disjoint and have the same length, the 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.
Sample Input 1
3
1 2 3
Sample Output 1
1 3
1 2 3
Sample Input 2
4
4 3 2 1
Sample Output 2
4 1
1
2
3
4
Sample Input 3
7
2 1 6 5 7 3 4
Sample Output 3
2 3
1 3 5
2 6 7
Explanation for Sample Output 3
The length of the longest increasing subsequence is
Comments