Code Submission Evaluation System Login

BOI 2016, day 2

Start:2016-05-13 09:00:00
End:2016-05-13 14:00:00
 

Tasks | Scoreboard | Statistics


CSES - BOI 2016, day 2 - SwapCSES - Swap

Swap

Time limit:1.00 s
Memory limit:256 MB

You are given a sequence of $n$ numbers $x_1,x_2,\ldots,x_n$. Each number $1,2,\ldots,n$ appears exactly once in the sequence.

You can modify the sequence using swaps. There are $n-1$ consecutive turns numbered $k=2,3,\ldots,n$. On turn $k$ you can either swap values $x_k$ and $x_{\lfloor k/2 \rfloor}$ in the sequence or do nothing.

Sequence $a_1,a_2,\ldots,a_n$ is lexicographically smaller than sequence $b_1,b_2,\ldots,b_n$ if there exists an index $j$ ($1 \le j \le n$) such that $a_k=b_k$ for all $k<j$ and $a_j<b_j$.

What is the lexicographically minimal sequence you can obtain?

Input

The first input line contains an integer $n$.

The second input line contains $n$ integers: the numbers in the sequence.

Output

You should output $n$ integers: the lexicographically minimal sequence.

Example

Input:
5
3 4 2 5 1


Output:
2 1 3 4 5

Subtask 1 (10 points)
Subtask 2 (11 points)
Subtask 3 (27 points)
Subtask 4 (20 points)
Subtask 5 (32 points)