|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||256 MB||36||6||5||21.739%|
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.
You should output n integers: the lexicographically minimal sequence.
5 3 4 2 5 1
2 1 3 4 5