该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Statement

Stalin's sort is a very simple, crude, and fast sort, inspired by the Soviet Great Purge. It aims to eliminate out-of-place elements rather than greedily sorting them correctly, thus reducing its time complexity to $O(n)$.

The specific method is: start with the second element in the array and delete it if it is strictly less than the previous element (ignoring any elements that have already been deleted). Continue traversing the array until it is sorted in non-descending order. For example, the array $[1, 4, 2, 3, 6, 5, 5, 7, 7]$ results in $[1, 4, 6, 7, 7]$ after Stalin's sort.

Now, please complete Stalin's sort and output the sorted result.

Input

The first line contains an integer $n$ ( $1 \le n \le 2\times 10^5$ ) that represents the size of the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le 10^9$ )

Output

The output represents the result of the array after Stalin sorting, separated by spaces.

Samples

7
3 6 4 9 2 5 2

3 6 9

5
5 4 4 2 2

5

8
2 2 4 4 6 6 10 10

2 2 4 4 6 6 10 10