퀵소트 킬러

N개의 정수를 오름차순으로 정렬하여라. 테스트 데이터에는 역순 정렬, 동일한 값의 대량 입력 등이 포함된다. 단순한 퀵소트 구현은 최악의 경우 O(N^2)이 된다.

입력

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

• 1 ≤ N ≤ 5,000,000
• -10^9 ≤ 각 수 ≤ 10^9

출력

정렬된 수를 공백으로 구분하여 출력한다.

예제 입력 1

5
3 1 4 1 5

예제 출력 1

1 1 3 4 5