Problem A
Around the Apex

Alice really likes permutation problems, so she created one just for you. You are given a permutation $p_1, p_2, \dots , p_n$ of the integers from $1$ to $n$. An operation consists of picking an index $2 \leq i \leq n - 1$ such that $p_i > \max (p_{i - 1}, p_{i + 1})$, then swapping $p_{i - 1}, p_{i + 1}$. Determine the lexicographically smallest permutation you can get after performing zero or more such operations on $p_1, p_2, \dots , p_n$.

Note: a sequence $a_1, \dots , a_n$ is lexicographically smaller than a sequence $b_1, \dots , b_n$ if and only if there exists an index $1 \leq i \leq n$ such that $a_i < b_i$ and for all $1 \leq j < i$, $a_j = b_j$.

Input

The first line of input contains an integer $n$ $(1 \leq n \leq 2 \cdot 10^5)$, the size of the permutation.

The next line contains $n$ space-separated integers $p_1, p_2, \dots , p_n$ $(1 \leq p_i \leq n)$, denoting the initial permutation. It is guaranteed that $p_1, p_2, \dots , p_n$ form a permutation of $1, 2, \dots , n$.

Output

Output $n$ space-separated integers in a single line: the lexicographically smallest permutation you can get after performing zero or more such operations on the initial permutation.

Sample 1 Explanation

We pick $i = 4$ and swap $p_3, p_5$, which results in the permutation $[1, 4, 2, 6, 5, 3]$. It can be shown this is the lexicographically smallest.

Sample 2 Explanation

We perform the following operations:

• Pick $i = 4$ to swap $p_3, p_5$, getting $[4, 5, 1, 8, 3, 6, 7, 2]$.

• Pick $i = 2$ to swap $p_1, p_3$, getting $[1, 5, 4, 8, 3, 6, 7, 2]$.

• Pick $i = 4$ to swap $p_3, p_5$, getting $[1, 5, 3, 8, 4, 6, 7, 2]$.

• Pick $i = 7$ to swap $p_6, p_8$, getting $[1, 5, 3, 8, 4, 2, 7, 6]$.

It can be shown this is the lexicographically smallest.

6
1 4 5 6 2 3

1 4 2 6 5 3

8
4 5 3 8 1 6 7 2

1 5 3 8 4 2 7 6