题目描述

给定一个包含 $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 \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$ 个整数，表示你能得到的字典序最小的序列。

样例

输入

5
3 4 2 5 1

输出

2 1 3 4 5

数据范围与提示

子任务, 分数, 数据范围

1, 10, $1 \leq n \leq 20$

2, 11, $1 \leq n \leq 40$

3, 27, $1 \leq n \leq 1000$

4, 20, $1 \leq n \leq 5 \cdot 10^4$

5, 32, $1 \leq n \leq 2 \cdot 10^5$