P4785 [BalticOI 2016] Swap (Day2)

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?

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

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

|Subtask|Score|Constraints| |:-:|:-:|-| |1|10|$1 \leq n \leq 20$| |2|11|$1 \leq n \leq 40$| |3|27|$1 \leq n \leq 1000$| |4|20|$1 \leq n \leq 5 \cdot 10^4$| |5|32|$1 \leq n \leq 2 \cdot 10^5$| Translated by ChatGPT 5