시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 73 11 10 23.810%

문제

1부터 n까지의 정수가 단 한 번씩만 등장하는 크기가 n인 수열 x1, x2, ..., xn이 주어진다.

두 수를 바꾸는 "스왑"이라는 연산을 통해 수열을 수정할 수 있다. k=2, 3, ..., n 순서대로 k를 증가시키면서 xk와 x⌊k/2⌋를 바꿀지 말지 선택할 수 있다.

수열 a1, a2, ..., an이 수열 b1, b2, ..., bn보다 사전순으로 앞선다는 것은 k < j인  k에 대해 ak = bk를 만족하고 aj < bj를 만족하는 j (1 ≤ j ≤ n)가 존재한다는 것을 의미한다.

순서대로 "스왑" 연산을 하여 만들 수 있는 수열 중 가장 사전순으로 앞선 수열은 어떤 것일까?

입력

입력의 첫 줄에 정수 n이 주어진다.

둘째 줄에는 수열을 나타내는 n개의 정수가 공백으로 구분되어 주어진다.

  • 1 ≤ n ≤ 2 ⋅ 105

출력

첫 줄에 순서대로 "스왑" 연산을 하여 만들 수 있는 수열 중 가장 사전순으로 앞선 수열을 나타내는 n개의 정수를 공백으로 구분하여 출력한다.

예제 입력

5
3 4 2 5 1

예제 출력

2 1 3 4 5

힌트

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2016 6번