题目描述

给定一个包含 $n$ 个数的序列 $x_1,x_2,\dots,x_n$。$1,2,\dots,n$ 每个数在序列中刚好出现一次。
你可以通过交换修改这个序列。你需要进行连续的 $n-1$ 轮操作，编号 $k=2,3,\dots,n$，第 $k$ 轮你可以选择交换 $xk$ 和 $x{\lfloor k/2\rfloor}$ 或是什么都不做。
如果存在一个数 $j(1 \leq j \leq n)$，使得对于所有 $k < j$ 且 $a_j < b_j,$ $a_k = b_k$ 成立，那么序列 $a_1\dots a_n$ 「字典序小于」序列 $b_1\dots b_n$。
你能得到的字典序最小的序列是什么？

输入格式

第一行，一个整数 $n$。
第二行，$n$ 个整数，表示序列 $x_1,x_2,\dots,x_n$。

输出格式

输出 $n$ 个整数，表示你能得到的字典序最小的序列。

样例

input

5
3 4 2 5 1

output

2 1 3 4 5

数据范围与提示