Disjoint Longest Increasing Subsequences Extraction

Given a permutation \(p\) of \(1\) to \(n\), let \(L\) be the length of its longest increasing subsequence (LIS). Your task is to extract as many disjoint (non‐overlapping) increasing subsequences as possible from \(p\) such that each extracted subsequence has length exactly \(L\). If a valid subsequence of length \(L\) cannot be found among the remaining elements, you must stop. Output the maximum number \(k\) of such subsequences and then output each subsequence in the order of extraction. All elements in each subsequence must appear in their original order in \(p\>.

Note: Two subsequences are disjoint if they do not share any index in \(p\>. There may be many valid schemes; you only need to output one.

inputFormat

The first line contains an integer \(n\) (the length of the permutation). The second line contains \(n\) distinct integers \(p_1, p_2, \dots, p_n\) — a permutation of \(1, 2, \dots, n\).

outputFormat

In the first line, output two integers \(k\) and \(L\) where \(k\) is the maximum number of disjoint increasing subsequences extracted and \(L\) is the length of the longest increasing subsequence of \(p\). Then output \(k\) lines, each containing \(L\) integers representing a valid extracted increasing subsequence (in the order they appear in \(p\)).

sample

5
3 1 2 5 4

1 3
1 2 5