 Code Submission Evaluation System Login

# BOI 2016, day 2

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

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)
• $1 \le n \le 20$
Subtask 2 (11 points)
• $1 \le n \le 40$
Subtask 3 (27 points)
• $1 \le n \le 1000$
Subtask 4 (20 points)
• $1 \le n \le 5 \cdot 10^4$
Subtask 5 (32 points)
• $1 \le n \le 2 \cdot 10^5$