Description

给定一个长度为n的序列Xn，该序列中没有重复的数字。

你有n-1次操作的机会：在每次操作机会时对应的有着k=2,3,4,...n,（在第1次交换机会时k=2,以此类推）

你可以交换X[k]和X[k/2],也可以不进行操作。求在执行完操作后，最小字典序的序列。

Format

Input

第一行：数列的长度n

第二行：长度为n的数列

1<=n<=2*(10^5)

Output

长度为n的数列

Samples

5
3 4 2 5 1

2 1 3 4 5