Problem Description

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

You may modify this sequence by swapping. You must perform $n - 1$ consecutive rounds of operations, numbered $k = 2, 3, \dots, n$. In round $k$, you may choose to swap $x_k$ and $x_{\lfloor k/2 \rfloor}$, or do nothing.

If there exists a number $j$ $(1 \leq j \leq n)$ such that for all $k < j$, $a_k = b_k$ holds, and $a_j < b_j$, then the sequence $a_1 \dots a_n$ is "lexicographically smaller" than the sequence $b_1 \dots b_n$.

What is the lexicographically smallest sequence you can obtain?

Input Format

The first line contains an integer $n$.
The second line contains $n$ integers, representing the sequence $x_1, x_2, \dots, x_n$.

Output Format

Output $n$ integers, representing the lexicographically smallest sequence you can obtain.

5
3 4 2 5 1

2 1 3 4 5

Hint

Translated by ChatGPT 5