Interview Queue

문제

A very popular position has just opened up at Poodle Inc. Candidates have formed a queue while they wait for their turn to be interviewed.

Competition is fierce and each candidate knows that they will not be selected if another candidate is strictly better than them. Every minute, each candidate looks at the resumé of candidates who are currently adjacent to them in the queue (ahead and behind). If at least one of the neighbour's resumé's perceived value is strictly greater than their resumé's perceived value, they leave the queue since they do not want to waste their time. The candidates all look at their neighbor's resumé simultaneously, and then some candidates leave the queue simultaneously.

This process continues until no more candidates leave the queue. Determine the number of minutes that pass while this process takes place. Report the values of the candidates that leave the queue in each round. Also report the final state of the queue.

입력

The first line of input contains a single integer $NN$ ($1\le N\le 1000001\; \backslash leq\; N\; \backslash leq\; 100\backslash ,000$), which is the number of candidates.

The second line contains $NN$ integers $v_1,\dots ,v_{N}v\_1,\; \backslash ldots,\; v\_N$ ($0\le v_i\le {10}^{9}0\; \backslash leq\; v\_i\; \backslash leq\; 10^9$ for each $1\le i\le N1\; \backslash leq\; i\; \backslash leq\; N$), where $v_{i}v\_i$ is the perceived value of the $i^{\text{th}}i^\backslash textrm\{th\}$ candidate.

출력

Display $MM$, the number of minutes taken by this process. Then display $MM$ lines. The $i^{\text{th}}i^\backslash textrm\{th\}$ line should contain the perceived values of the candidates who left the queue in the $i^{\text{th}}i^\backslash textrm\{th\}$ minute in the same relative order that they appeared in the queue. Finally display a line indicating the final list of perceived values in the queue after candidates no longer leave it.