수 정렬하기 (대용량)

N개의 정수를 오름차순으로 정렬하여 출력한다. 데이터 양이 많으므로 O(N log N) 알고리즘을 사용하라.

입력

첫째 줄에 정수의 개수 N이 주어진다.
둘째 줄에 N개의 정수가 공백으로 구분되어 주어진다.

• 1 ≤ N ≤ 100,000
• -1,000,000 ≤ 각 정수 ≤ 1,000,000

출력

오름차순으로 정렬한 N개의 정수를 공백으로 구분하여 한 줄에 출력한다.

예제 입력 1

5
3 1 4 1 5

예제 출력 1

1 1 3 4 5