Problem D
Safe Dictator Sort

It is well-known that a correct comparison-based sorting algorithm cannot use fewer than $O(N\log (N))$ comparisons in the worst case if the algorithm can only compare and swap elements. To get around this, the algorithm dictator sort was developed. It sorts a list as follows:

Always keep the first element. For each subsequent element $x$, compare $x$ to the most recently kept element. If $x$ is strictly larger, keep it. Otherwise, remove $x$ from the list and send it to a training camp. The training camp is a list to which new elements are appended at the back.

For example, if the list is $[2,1,4,5,3,7]$, the remaining list will be $[2,4,5,7]$, and the training camp contains $[1,3]$. This algorithm can be implemented in $O(N)$ time, but it sacrifices correctness.

To try to fix this, you decide to modify the algorithm. Your idea is to run dictator sort again on the list in the training camp. You then get a new training camp on which you run dictator sort again, and so on, until the training camp becomes empty. When the algorithm finishes, you have several lists that are all sorted; then you are done. It is unclear what this is good for, but it feels like you have really advanced the state of the art. Therefore, you decide to name your new algorithm safe dictator sort.

For example, suppose safe dictator sort is run on the list $[5,3,1,4]$. After the first step, the result is the list $[5]$ and the training camp $[3,1,4]$. If dictator sort is then run on the training camp, the result is $[3,4]$ and the new training camp is $[1]$. Since $[1]$ is sorted, the algorithm terminates. The final result is the three lists $[5]$, $[3,4]$, and $[1]$.

Unfortunately, safe dictator sort is no longer as fast as ordinary dictator sort. Can you implement the algorithm efficiently? That is, after each time dictator sort is run, output the resulting sorted list, until the algorithm finishes.

Input

The first line of input contains the integer $N$ ($1 \leq N \leq 2 \cdot 10^5$), the number of integers in the list.

The second line of input contains $N$ integers $a_1, \dots , a_N$ ($1 \leq a_i \leq 10^6$), the integers in the list to be “sorted”.

Output

Print the contents of the sorted list on its own line after each time ordinary dictator sort is run, including the last one.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

4
5 3 1 4

5 
3 4 
1 

5
5 3 4 2 1

5 
3 4 
2 
1 

3
1 1 1

1 
1 
1