시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 6 0 0 0.000%

문제

You are given a sequence of n numbers x1, x2, ..., xn. Each number 1, 2, ..., n appears exactly once in the sequence.

You can modify the sequence using swaps. There are n - 1 consecutive turns numbered k = 2, 3, ..., n. On turn k you can either swap xk values x\(\lfloor\)k/2\(\rfloor\) and in the sequence or do nothing.

Sequence a1, a2, ..., an is lexicographically smaller than sequence b1, b2, ..., bn if there exists an index j (1 ≤ j ≤ n) such that ak = bk for all k < j and aj < bj.

What is the lexicographically minimal sequence you can obtain?

입력

The first input line contains an integer n.

The second input line contains n integers: the numbers in the sequence.

  • 1 ≤ n ≤ 2 ⋅ 105

출력

You should output n integers: the lexicographically minimal sequence.

예제 입력

5
3 4 2 5 1

예제 출력

2 1 3 4 5

힌트