#include <iostream>
using namespace std;
int N; // 정려할 숫자의 개수
int arr[10000005]; // 정렬할 숫자 배열
// 삽입 정렬
void InsertSort(int left, int right) {
// 왼쪽+1 부터 key 설정
for (int i=left+1; i<=right; i++) {
int key = arr[i];
int j;
// key가 배열의 값보다 작은 경우 밀고 큰 경우 삽입
for (j=i-1; j>=left; j--) {
if (key < arr[j]) {
arr[j+1] = arr[j];
}
else {
break;
}
}
arr[j+1] = key;
}
}
// 퀵소트
void QuickSort(int left, int right) {
if (left >= right) return; // 만약 왼쪽이 오른쪽보다 크다면 종료
// 크기가 작은 경우 삽입 정렬으로
if (right-left<40) { InsertSort(left, right); return; }
int pivot = left; // 피벗은 처음으로 설정
int low = left+1, high = right; // low, high 설정
int temp; // 교환을 위한 인자 설정
// 포인터가 엇갈리면 종료
while(low <= high) {
// low를 pivot보다 큰 수가 나올 때까지 탐색
while(low <= right && arr[low] <= arr[pivot]) {
low++;
}
// high를 pivot보다 작은 수가 나올 때까지 탐색
while (high > left && arr[high] >= arr[pivot]) {
high--;
}
// 포인터가 엇갈린 경우
if (low > high) {
temp = arr[high];
arr[high] = arr[pivot];
arr[pivot] = temp;
}
// 그 전에는 계속 스왑
else {
temp = arr[low];
arr[low] = arr[high];
arr[high] = temp;
}
}
// 피벗 기준으로 왼쪽과 오른쪽에 대해 퀵소트
QuickSort(left, high-1);
QuickSort(high+1, right);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
for (int i=0; i<N; i++) {
cin >> arr[i];
}
QuickSort(0, N-1);
for (int i=0; i<N; i++) {
cout << arr[i] << endl;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBOOyAvLyDsoJXroKTtlaAg7Iir7J6Q7J2YIOqwnOyImAppbnQgYXJyWzEwMDAwMDA1XTsgLy8g7KCV66Cs7ZWgIOyIq+yekCDrsLDsl7QKCi8vIOyCveyehSDsoJXroKwKdm9pZCBJbnNlcnRTb3J0KGludCBsZWZ0LCBpbnQgcmlnaHQpIHsKCQogIAkvLyDsmbzsqr0rMSDrtoDthLAga2V5IOyEpOyglQoJZm9yIChpbnQgaT1sZWZ0KzE7IGk8PXJpZ2h0OyBpKyspIHsKCQlpbnQga2V5ID0gYXJyW2ldOwoJCWludCBqOwogICAgICAKICAgICAgCS8vIGtleeqwgCDrsLDsl7TsnZgg6rCS67O064ukIOyekeydgCDqsr3smrAg67CA6rOgIO2BsCDqsr3smrAg7IK97J6FCgkJZm9yIChqPWktMTsgaj49bGVmdDsgai0tKSB7CgkJCWlmIChrZXkgPCBhcnJbal0pIHsKCQkJCWFycltqKzFdID0gYXJyW2pdOwoJCQl9CgkJCWVsc2UgewoJCQkJYnJlYWs7CgkJCX0KCQl9CgkJYXJyW2orMV0gPSBrZXk7Cgl9Cn0KCgovLyDtgLXshoztirgKdm9pZCBRdWlja1NvcnQoaW50IGxlZnQsIGludCByaWdodCkgewoJCglpZiAobGVmdCA+PSByaWdodCkgcmV0dXJuOyAvLyDrp4zslb0g7Jm87Kq97J20IOyYpOuluOyqveuztOuLpCDtgazri6TrqbQg7KKF66OMCgkKCS8vIO2BrOq4sOqwgCDsnpHsnYAg6rK97JqwIOyCveyehSDsoJXroKzsnLzroZwKCWlmIChyaWdodC1sZWZ0PDQwKSB7IEluc2VydFNvcnQobGVmdCwgcmlnaHQpOyByZXR1cm47IH0KCQoJaW50IHBpdm90ID0gbGVmdDsgLy8g7ZS867KX7J2AIOyymOydjOycvOuhnCDshKTsoJUKCWludCBsb3cgPSBsZWZ0KzEsIGhpZ2ggPSByaWdodDsgLy8gbG93LCBoaWdoIOyEpOyglQoJaW50IHRlbXA7IC8vIOq1kO2ZmOydhCDsnITtlZwg7J247J6QIOyEpOyglQoJCgkvLyDtj6zsnbjthLDqsIAg7JeH6rCI66as66m0IOyiheujjAoJd2hpbGUobG93IDw9IGhpZ2gpIHsKCQkKCQkvLyBsb3frpbwgcGl2b3Trs7Tri6Qg7YGwIOyImOqwgCDrgpjsmKwg65WM6rmM7KeAIO2DkOyDiQoJCXdoaWxlKGxvdyA8PSByaWdodCAmJiBhcnJbbG93XSA8PSBhcnJbcGl2b3RdKSB7CgkJCWxvdysrOwoJCX0KCQkKCQkvLyBoaWdo66W8IHBpdm9067O064ukIOyekeydgCDsiJjqsIAg64KY7JisIOuVjOq5jOyngCDtg5Dsg4kKCQl3aGlsZSAoaGlnaCA+IGxlZnQgJiYgYXJyW2hpZ2hdID49IGFycltwaXZvdF0pIHsKCQkJaGlnaC0tOwoJCX0KCQkKCQkvLyDtj6zsnbjthLDqsIAg7JeH6rCI66awIOqyveyasCAKCQlpZiAobG93ID4gaGlnaCkgewoJCQl0ZW1wID0gYXJyW2hpZ2hdOwoJCQlhcnJbaGlnaF0gPSBhcnJbcGl2b3RdOwoJCQlhcnJbcGl2b3RdID0gdGVtcDsKCQl9CgkJCgkJLy8g6re4IOyghOyXkOuKlCDqs4Tsho0g7Iqk7JmRCgkJZWxzZSB7CgkJCXRlbXAgPSBhcnJbbG93XTsKCQkJYXJyW2xvd10gPSBhcnJbaGlnaF07CgkJCWFycltoaWdoXSA9IHRlbXA7CgkJfQoJCQoJCQoJfQoJCgkvLyDtlLzrspcg6riw7KSA7Jy866GcIOyZvOyqveqzvCDsmKTrpbjsqr3sl5Ag64yA7ZW0IO2AteyGjO2KuAoJUXVpY2tTb3J0KGxlZnQsIGhpZ2gtMSk7CglRdWlja1NvcnQoaGlnaCsxLCByaWdodCk7CgkKfQoKaW50IG1haW4oKSB7CgkKCWlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogICAgY2luLnRpZShOVUxMKTsKICAgIGNvdXQudGllKE5VTEwpOwoJCgljaW4gPj4gTjsKCQoJZm9yIChpbnQgaT0wOyBpPE47IGkrKykgewoJCWNpbiA+PiBhcnJbaV07Cgl9CgkKCVF1aWNrU29ydCgwLCBOLTEpOwoJCglmb3IgKGludCBpPTA7IGk8TjsgaSsrKSB7CgkJY291dCA8PCAgYXJyW2ldIDw8IGVuZGw7Cgl9CgkKCQoJCglyZXR1cm4gMDsKfQ==