暂无测试数据。

背景

想出来学姐会奖励你鸭翅和威化

描述

一个n个数的序列x1, x2,…, xn。每一个数值1,2，…，n在序列中恰好出现一次。
您可以使用互换来修改序列。你可以进行n−1个连续的互换（按顺序），编号为k = 2，3，…，n。在第K轮，你可以交换序列xk的和x【k/2】的值或什么都不做。
序列a1，a2，…，an是字典序小于序列b1, b2,…, bn的条件是：如果存在一个编号j（1≤j≤n），使所有的k（k<j）都有ak = bk并且还有aj <bj。
输出你出得到的字典序最小的序列？（不如跳舞）

输入：

第一行包含一个整数n。
第二行包含n个整数：数列中的数。

输出：

你应该输出n个数：你能得到的字典序最小的序列。

样例：

Input1:

5
3 4 2 5 1

Output1:

2 1 3 4 5

Input2:

20
7 8 4 12 6 19 1 5 16 14 15 20 17 18 9 10 13 11 2 3

Output2:

4 6 1 5 7 8 9 10 2 3 15 20 17 18 19 12 13 11 16 14

Input3:

20
7 8 4 12 6 19 1 5 16 14 15 20 17 18 9 10 13 11 2 3

Output3:

4 6 1 5 7 8 9 10 2 3 15 20 17 18 19 12 13 11 16 14

Input4:

40
19 15 20 27 16 11 34 5 21 6 30 3 40 39 12 2 7 13 1 23 37 32 18 28 25 17 33 31 29 36 4 22 10 35 8 14 9 38 26 24

Output4:

15 16 11 5 6 3 12 2 1 19 18 20 17 29 4 10 7 9 13 23 37 30 32 28 25 40 33 31 34 36 39 22 27 35 8 14 21 38 26 24

Input5:

20 
3 19 17 5 8 14 12 6 15 7 9 4 10 1 20 16 18 13 11 2

Output5:

3 5 12 6 7 4 1 16 11 2 9 14 10 17 20 19 18 13 15 8

提示：

然而学姐并没有给我范围让我想，她表示有n^2的，还有n *sqrt（n）的 ，？？？？
并不一定是十万，只是我猜测的，毕竟她说想出什么复杂度的算法 她给什么复杂度范围的数据