Greedy Increasing Subsequences

문제

Jimmy's homework is to find a long increasing subsequence of a given sequence $a_1,a_2,\dots ,a_{n}a\_1,\; a\_2,\; \backslash ldots,\; a\_n$. But the sequence is really long! Jimmy doesn't know how to do this effectively.

So Jimmy takes a greedy approach. He begins by picking the first number in the sequence. Then he repeats the following rule until it no longer applies: pick the next number in the sequence that is bigger than the number he just picked.

More precisely, Jimmy picks the subsequence $a_{i_1},a_{i_2},\dots ,a_{i_k}a\_\{i\_1\},\; a\_\{i\_2\},\; \backslash ldots,\; a\_\{i\_k\}$ where:

• $i_1=1i\_1\; =\; 1$
• For each , $i_{j+1}i\_\{j+1\}$ is the smallest index greater than $i_{j}i\_j$ such that
• $a_{i_k}\ge a_{\mathrm{\ell }}a\_\{i\_k\}\; \backslash geq\; a\_\backslash ell$ for every $\mathrm{\ell }>i_k\backslash ell\; >\; i\_k$

Jimmy realizes that this may not produce a very long subsequence. So to help him find other subsequences, he removes $a_{i_1},a_{i_2},\dots ,a_{i_k}a\_\{i\_1\},\; a\_\{i\_2\},\; \backslash ldots,\; a\_\{i\_k\}$ from the given sequence and finds another increasing subsequence using his greedy algorithm on the remaining sequence. He repeats this until he has used up all numbers from the original sequence.

But even this is starting to sound exhausting for Jimmy, so he asks you to help him by finding all of the sequences that would be formed by repeatedly applying the above greedy procedure and removing the resulting subsequence until the given sequence is empty.

입력

The first line of input contains a single integer $nn$ ($1\le n\le 2\times {10}^{5}1\; \backslash leq\; n\; \backslash leq\; 2\; \backslash times\; 10^5$) indicating the length of the original sequence.

The second line of input contains $nn$ integers $a_1,a_2,\dots ,a_{n}a\_1,\; a\_2,\; \backslash ldots,\; a\_n$ ($0\le a_i\le {10}^{9}0\; \backslash leq\; a\_i\; \backslash leq\; 10^9$).

출력

The first line of output contains the number $ss$ of sequences that are produced. The next $ss$ lines contain the sequences, the $ii$th such line containing the increasing subsequence that is formed in the $ii$th application of the greedy algorithm.

7
2 2 1 5 3 4 6

3
2 5 6
2 3 4
1

7
8 6 7 5 3 0 9

5
8 9
6 7
5
3
0