영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
It is well-known that a correct comparison-based sorting algorithm cannot use fewer than O(Nlog(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 ≤ N ≤ 2 · 10^5), the number of integers in the list.
The second line of input contains N integers a_1, …, a_N (1 ≤ a_i ≤ 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. To earn points for a group, you must pass all test cases in that group.
| Group | Points | Constraints |
|---|---|---|
| 1 | 15 | N ≤ 100 |
| 2 | 30 | N ≤ 5000 |
| 3 | 10 | a_i ≤ 2 |
| 4 | 14 | a_i ≤ 10 |
| 5 | 31 | No additional constraints. |
예제
예제 1
4 5 3 1 4
5 3 4 1
예제 2
5 5 3 4 2 1
5 3 4 2 1
예제 3
3 1 1 1
1 1 1