농장의 번갈아 점검

문제

농장에는 일렬로 놓인 N개의 재배 칸이 있다. 각 칸에는 왼쪽부터 차례대로 1번부터 N번까지 번호가 붙어 있다. 농장 관리 로봇은 모든 칸의 흙 상태를 한 번씩 점검하려 한다. 로봇은 전체 구간의 가운데 칸을 먼저 확인한 뒤, 남은 구간을 더 작은 구간으로 나누어 점검하는 규칙을 사용한다. 하나의 점검 작업은 연속한 구간 [L, R]과 깊이 d로 표현한다. L이 R보다 크면 그 구간에는 칸이 없으므로 아무 일도 하지 않고 해당 작업을 끝낸다. 칸이 있는 구간에서는 먼저 M = ⌊(L + R) / 2⌋번 칸을 점검한다. 여기서 ⌊x⌋는 x 이하인 가장 큰 정수를 뜻한다. 따라서 구간에 칸이 짝수 개 있으면 가운데의 두 칸 중 번호가 작은 칸을 먼저 점검한다. 가운데 칸의 점검을 마치면 왼쪽 구간 [L, M - 1]과 오른쪽 구간 [M + 1, R]을 각각 하나의 새 작업으로 처리한다. 두 새 작업의 깊이는 모두 d + 1이다. 현재 깊이 d가 짝수이면 왼쪽 구간의 작업 전체를 끝낸 다음 오른쪽 구간의 작업을 시작한다. 현재 깊이 d가 홀수이면 오른쪽 구간의 작업 전체를 끝낸 다음 왼쪽 구간의 작업을 시작한다. 작업 전체를 끝낸다는 것은 그 작업에서 다시 만들어지는 더 작은 구간들의 점검까지 모두 마친다는 뜻이다. 따라서 두 구간의 점검을 한 칸씩 번갈아 진행하는 것은 아니다. 칸이 하나뿐인 구간에서는 그 칸만 점검하고 작업을 끝낸다. 빈 구간은 점검 순서에 아무 번호도 추가하지 않는다. 로봇의 첫 작업은 구간 [1, N]을 깊이 0으로 처리하는 것이다. 이동 시간이나 칸 사이의 거리는 고려하지 않는다. 주어진 규칙에 따라 로봇이 점검하는 칸의 번호를 처음부터 마지막까지 순서대로 출력하는 프로그램을 작성한다.

입력

첫째 줄에 재배 칸의 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 100,000이다.

출력

점검하는 칸의 번호 N개를 점검 순서대로 공백으로 구분하여 한 줄에 출력한다. 각 번호는 정확히 한 번씩 나타나야 한다.

1

1

6

3 1 2 5 6 4

7

4 2 3 1 6 7 5

출처: Devin.KR 자체 제작