충전 모듈 점검 배열

문제

한 전기차 충전소는 교체용 충전 모듈을 정기적으로 점검한다. 점검 전에 각 모듈의 남은 시험 시간을 분 단위의 양의 정수로 측정해 배열에 저장한다. 배열의 각 원소는 모듈 하나의 시험 시간이며, 서로 다른 모듈의 시험 시간이 같을 수도 있다. 처음 저장된 배열의 순서는 실제 점검 순서와 관계가 없다. 담당자는 짧은 시험과 긴 시험을 번갈아 배치하기 위해 다음 규칙으로 새 배열을 만든다. 먼저 아직 선택하지 않은 모듈 중 시험 시간이 가장 작은 모듈 하나를 선택해 새 배열의 끝에 추가한다. 다음에는 남은 모듈 중 시험 시간이 가장 큰 모듈 하나를 선택해 새 배열의 끝에 추가한다. 이후에도 가장 작은 시간, 가장 큰 시간의 순서로 선택을 번갈아 반복한다. 첫 번째 선택은 언제나 가장 작은 시간이다. 한 번 선택한 모듈은 남은 모듈에서 제거한다. 모듈이 하나만 남았다면 그 모듈을 추가하고 작업을 끝낸다. 선택해야 할 시간이 같은 모듈이 여러 개라면 어느 모듈을 선택해도 된다. 출력에는 모듈의 식별 번호가 아니라 시험 시간만 기록하므로 이러한 선택은 출력 결과에 영향을 주지 않는다. 담당자가 필요한 것은 이 규칙을 끝까지 적용했을 때 만들어지는 시험 시간의 나열이다. 시험 시간을 합치거나 평균으로 바꾸지 않으며, 시간이 같은 원소도 입력에 등장한 개수만큼 모두 유지한다. 모든 모듈을 정확히 한 번씩 선택한 새 배열을 출력하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N이 주어진다. 1≤N≤60,000이다.
둘째 줄에 각 모듈의 시험 시간을 나타내는 정수 A1, A2, …, AN이 공백으로 주어진다. 모든 i에 대해 1≤Ai≤99,999이다. 같은 값이 여러 번 주어질 수 있다.

출력

규칙에 따라 만든 새 배열의 원소 N개를 순서대로 공백으로 구분하여 한 줄에 출력한다.

5
18 4 11 7 25

4 25 7 18 11

6
8 3 8 3 5 5

3 8 3 8 5 5

1
1

1

출처: Devin.KR 자체 제작