2

만조, 간조

시간제한 : 1초

우리나라에서 조수간만의 차가 가장 큰 서해의 가로림만 근처에서, 동아리 셈틀이 며칠 동안 자연탐사 활동 중이다. 진짜 조수간만의 차가 가장 큰지 확인해 보고 싶었던 경곽이는 지구과학 시간에 배운 지식을 바탕으로, 매일 만조/간조 시간에 보트를 타고 나간 후, 똑같은 위치에서 바닷물의 깊이를 측정해 두었다.

하지만 자연탐사 활동 마지막 날, 매우 센 바람이 불어, 며칠 동안 측정해 두었던 측정 자료들의 순서가 섞여 버렸다.

하지만, 다음과 같이 생각할 수 있었다.

- 간조(바닷물이 가장 많이 빠진) 때 수심을 측정한 후, 만조(바닷물이 가장 많이 들어왔을 때) 때 다시 수심을 측정했고, 그렇게 매일 반복해서 측정했다.

- 만조 때의 수심들은 모든 간조 때의 수심보다 깊었다.

- 만조 때의 수심은 계속 깊어지고, 간조 때의 수심은 계속 낮아졌다.

수심 데이터들이 순서 없이 주어질 때, 원래 측정되었던 수심 데이터로 복구해 보자.

입력형식

첫 줄에는 수심 측정 횟수(n)가 입력된다.([eqn: 1 LEQ n LEQ `100])

두 번째 줄에는 측정된 수심들(Mi)이 공백을 두고 입력된다.([eqn: 0 LEQ `M _{i} `` LEQ 1,000,000])

출력형식

원래 측정했던 수심 데이터를 출력한다.

입출력 예시

입력

8

10 50 40 7 3 110 90 2

출력

10 40 7 50 3 90 2 110

설명 : 간조는 10, 7, 3, 2 순서로, 만조는 40, 50, 90, 110 순서로 측정되었다.