Hide
Problem D
Sort of Sort
Sorting takes so long... but if we don’t mind losing some data we can sort of sort much faster!
A sort of sorted list is a monotonically increasing list containing all elements of another list $a$ that were originally in sorted order. That is, a sort of sorted list obtained from list $a$ contains all $a_i$ such that $a_i \ge a_j$ for all $0 \le j < i$.
Input
The first line of input contains a single integer $N$, the length of the unsorted list ($1 \le N \le 100\, 000$). The next line contains $N$ space separated integers $a_i$ ($-200\, 000 \le a_i \le 200\, 000$).
Output
Output a single line of space separated integers representing the sort of sorted list obtained from the given list $a$.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 3 1 7 |
3 7 |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 1 4 3 9 7 11 |
1 4 9 11 |
| Sample Input 3 | Sample Output 3 |
|---|---|
12 0 1 4 4 3 2 3 4 5 5 7 4 |
0 1 4 4 4 5 5 7 |
