Lexicographically Minimum Sequence

You are given a permutation of n distinct integers \(x_1, x_2, \dots, x_n\) which is a rearrangement of \(1,2,\dots,n\). You are allowed to perform exactly \(n-1\) operations sequentially. In the \(k\)-th round (for \(k=2,3,\dots,n\)) you may either swap \(x_k\) and \(x_{\lfloor k/2 \rfloor}\) or do nothing.

A sequence \(a_1,a_2,\dots,a_n\) is said to be lexicographically smaller than \(b_1,b_2,\dots,b_n\) if there exists an index \(j\) (\(1\le j\le n\)) such that \(a_i=b_i\) for all \(i<j\) and \(a_j < b_j\). Your task is to choose, for each round, whether to swap or not in order to obtain the lexicographically smallest sequence possible.

Operation details:

• For \(k=2,3,\dots,n\), let \(p=\lfloor k/2 \rfloor\). In round \(k\), you may swap \(x_k\) with \(x_p\) or leave the sequence unchanged.

Note: The operations are performed sequentially in the order of increasing \(k\). That is, the decision in round \(k\) is applied to the current sequence, which might have been modified by previous rounds.

Your goal is to obtain the lexicographically minimum final sequence.

inputFormat

The first line contains an integer \(n\) (\(2\le n\le 10\)). The second line contains \(n\) space-separated integers representing the permutation \(x_1,x_2,\dots,x_n\).

outputFormat

Output the lexicographically smallest sequence that can be obtained after performing the \(n-1\) rounds of operations. Print the \(n\) numbers separated by a single space.

sample

3
2 3 1

1 2 3