给定一个包含 $n$ 个数字的序列 $x_1, x_2, \dots, x_n$。每个数字 $1, 2, \dots, n$ 在序列中恰好出现一次。

你可以通过交换操作来修改序列。共有 $n-1$ 个连续的回合，编号为 $k = 2, 3, \dots, n$。在第 $k$ 回合，你可以选择交换序列中 $x_k$ 和 $x_{\lfloor k/2 \rfloor}$ 的值，或者什么都不做。

如果存在一个下标 $j$ ($1 \le j \le n$)，使得对于所有 $k < j$ 都有 $a_k = b_k$，且 $a_j < b_j$，则称序列 $a_1, a_2, \dots, a_n$ 字典序小于序列 $b_1, b_2, \dots, b_n$。

请问你能得到的字典序最小的序列是什么？

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数：序列中的数字。

输出格式

输出 $n$ 个整数：字典序最小的序列。

子任务

• 子任务 1（10 分）：$1 \le n \le 20$
• 子任务 2（11 分）：$1 \le n \le 40$
• 子任务 3（27 分）：$1 \le n \le 1000$
• 子任务 4（20 分）：$1 \le n \le 5 \cdot 10^4$
• 子任务 5（32 分）：$1 \le n \le 2 \cdot 10^5$

样例

输入格式 1

5
3 4 2 5 1

输出格式 1

2 1 3 4 5