두 벌씩 바뀐 세탁물

문제

한 세탁소에서는 포장이 끝난 세탁물을 긴 작업대 위에 한 줄로 놓는다. 각 포장에는 접수 번호가 하나씩 붙어 있으며, 서로 다른 포장의 접수 번호는 모두 다르다. 작업대의 위치는 왼쪽부터 1번, 2번, ..., N번으로 센다. 처음 i번 위치에 놓인 포장의 접수 번호를 A_i라고 한다. 직원은 두 포장을 한 묶음으로 확인하는 작업을 한다. 먼저 처음 배치의 1번과 2번 위치를 한 묶음으로 정하고, 그다음 3번과 4번 위치를 한 묶음으로 정한다. 같은 방법으로 왼쪽부터 겹치지 않게 두 위치씩 묶는다. 한 위치가 두 묶음에 동시에 속하는 일은 없다. 확인이 끝난 묶음은 두 포장의 자리를 서로 바꾸어 내려놓는다. 따라서 처음 1번 위치의 포장은 2번 위치로 가고, 처음 2번 위치의 포장은 1번 위치로 간다. 처음 3번과 4번 위치의 포장도 같은 방식으로 자리를 바꾼다. 이 작업은 처음 정한 각 묶음에 정확히 한 번씩만 적용한다. 세탁물 수 N이 홀수이면 맨 오른쪽에 포장 하나가 남는다. 이 포장은 짝이 없으므로 확인 과정에서 이동하지 않고 원래 위치에 그대로 둔다. N이 1이면 유일한 포장이 그대로 남는다. 포장의 접수 번호 자체는 바꾸지 않으며, 번호의 크기에 따라 순서를 정렬하는 작업도 하지 않는다. 모든 묶음의 확인이 끝난 후 직원은 작업대 왼쪽부터 접수 번호를 다시 기록하려 한다. 처음 배치된 접수 번호 목록이 주어질 때, 작업을 마친 뒤의 접수 번호 목록을 구하는 프로그램을 작성한다. 최종 목록에는 모든 접수 번호가 정확히 한 번씩 나타나야 하며, 각 번호는 작업 후 놓인 위치의 순서대로 출력해야 한다.

입력

첫째 줄에 세탁물 수 N이 주어진다.
둘째 줄에 처음 작업대의 왼쪽부터 접수 번호 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다.
모든 입력값은 정수이며, 1 ≤ N ≤ 1,000, 1 ≤ A_i ≤ 1,000이다. 모든 접수 번호는 서로 다르다.

출력

작업을 마친 뒤의 접수 번호 N개를 왼쪽부터 순서대로 한 줄에 공백으로 구분하여 출력한다.

5
41 18 63 27 90

18 41 27 63 90

1
72

72

출처: Devin.KR 자체 제작