/*#include <stdio.h>
typedef struct
{
int grade;
char name[100];
}student;
int main()
{
student stu[51],temp;
int n,b;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s %d",stu[i].name,&stu[i].grade);
}
for(int i=1;i<n;i++)
{
b=0;
for(int j=1;j<=n-i;j++)
{
if(stu[j].grade<stu[j+1].grade)
{
temp=stu[j];
stu[j]=stu[j+1];
stu[j+1]=temp;
b++;
}
}
if(b==0)
{
break;
}
}
printf("%s",stu[3].name);
}*/
/*#include<stdio.h>
typedef struct
{
int no,ma,in;
}student;
int main()
{
student stu[1001],temp;
int i,j,n,b;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d %d",&stu[i].ma,&stu[i].in);
stu[i].no=i;
}
for(i=1;i<n;i++)
{
b=0;
for(j=1;j<=n-i;j++)
{
if(stu[j].ma<stu[j+1].ma)
{
temp=stu[j];
stu[j]=stu[j+1];
stu[j+1]=temp;
b++;
}
if(stu[j].in<stu[j+1].in&&stu[j].ma==stu[j+1].ma)
{
temp=stu[j];
stu[j]=stu[j+1];
stu[j+1]=temp;
b++;
}
if(stu[j].no>stu[j+1].no&&stu[j].in==stu[j+1].in&&stu[j].ma==stu[j+1].ma)
{
temp=stu[j];
stu[j]=stu[j+1];
stu[j+1]=temp;
b++;
}
}
if(b==0)
{
break;
}
}
for(i=1;i<=n;i++)
{
printf("%d %d %d \n",stu[i].no,stu[i].ma,stu[i].in);
}
}*/
/*
#include <stdio.h>
int a[10001];
int n, i, j, temp, min;
int main() {
scanf("%d", &n);
for (i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (i=1; i<n; i++) {
min=i;
for (j=i+1; j<=n; j++) {
if(a[min]<a[j])
{
min=j;
}
}
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
for (i=1; i<=n; i++)
printf("%d ", a[i]);
return 0;
}
*/
/*
#include <stdio.h>
int a[10001];
int n, i, j, temp, key;
int main() {
scanf("%d", &n);
for (i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (i=2; i<=n; i++)
{
key=a[i];
for(j=i-1; a[j]<key&&j!=0 ;j--)
{
a[j+1]=a[j];
}
a[j+1]=key;
}
for (i=1; i<=n; i++)
printf("%d\n", a[i]);
return 0;
}
퀵정렬 quick_sort
기준값보다 작은값들은 왼쪽, 큰 값들은 오른쪽에 위치
*/
#include<stdio.h>
int a[100001];
void qs(int s, int e) // a[s] ~ a[e] 를 퀵정렬 하세요
{
int p=s,temp;
int l = s, h=e+1;
//기준값보다 작은값들은 왼쪽, 큰 값들은 오른쪽에 위치
do
{
do{ l++;}while(a[p]>a[l]);
do{ h--;}while(a[p]<a[h]);
if(l<h)
{
temp=a[l];
a[l]=a[h];
a[h]=temp;
}
}while(l<h);
// a[p] - 작은값 - 큰값
temp=a[p];
a[p]=a[h];
a[h]=temp;
// 작은값 -a[p] -큰값
if(s<h-1) qs(s,h-1);
if(h+1<e) qs(h+1,e);
}
int main()
{
int n,i;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
qs(1,n);
for(i=1;i<=n;i++)
{
printf("%d\n",a[i]);
}
}