Swap

A sequence $x_1, x_2, \dots, x_n$ of length $n$ is given. Every integer from $1$ to $n$ appears in it exactly once.

You can change the sequence with a "swap" operation that exchanges two numbers. Going through $k = 2, 3, \dots, n$ in that order, for each $k$ you can choose whether to exchange $x_k$ and $x_{\lfloor k/2 \rfloor}$. You cannot go back to a value of $k$ that you already passed.

A sequence $a_1, a_2, \dots, a_n$ comes before a sequence $b_1, b_2, \dots, b_n$ in lexicographic order when some $j$ $(1 \le j \le n)$ satisfies $a_k = b_k$ for every $k < j$ and $a_j < b_j$.

Among the sequences you can build by choosing the "swap" operations in this order, which one comes first in lexicographic order?

The first line contains the integer $n$. $(1 \le n \le 5000)$

The second line contains the $n$ integers of the sequence, separated by spaces. They form a permutation of the integers from $1$ to $n$.

On the first line, print the $n$ integers of the sequence that comes first in lexicographic order among the sequences you can build by choosing the "swap" operations in order, separated by spaces.