/*
#include <stdio.h>//2633 : Lower Bound
int a[100001]={};
int f(int s, int e, int k)
{
int mid=(s+e)/2;
if(s==e){ //(= s==e||e==mid || s==mid)결국 하나 남았다는 뜻
if(a[mid]<k){
return mid+1;
}
else{
return mid;
}
return mid;
}
if(a[mid]>=k){//down
return f(s,mid,k);
}
else{//up
return f(mid+1,e,k);
}
}
int main()
{
int i,n,k;
scanf("%d %d",&n,&k);
for(i=1; i<=n; i++){
scanf("%d",&a[i]);
}
printf("%d",f(1,n,k));
return 0;
}
*/
/*
#include <stdio.h>//3002 : 기억력 테스트 3
int a[1000001]={};
int f(int s, int e, int k)
{
int mid=(s+e)/2;
if(s==e){
if(a[mid]!=k){
return -1;
}
return mid;
}
else if(a[mid]<k){
return f(mid+1,e,k);
}
else{
return f(s,mid,k);
}
}
int main()
{
int i,j,n,m,k;
scanf("%d",&n);
for(i=1; i<=n; i++){
scanf("%d",&a[i]);
}
scanf("%d",&m);
for(i=1; i<=m; i++){
scanf("%d",&k);
printf("%d ",f(1,n,k));
}
return 0;
}
*/
/*
void qs(int s, int e) // a[s] ~ a[e]를 퀵정렬해라
{
if(s>=e) // 정렬할 데이터가 없거나 1개일때 종료
{
return;
}
int pivot = s;
int left = s+1, right=e;
while()
{
while()..left 증가
{
}
while()//right 증가
{
}
if(left>=right)
{
break;
}
// a[l], a[r] 교환
}
//a[r] a[pivot] 교환
// ....
//
// s left e
// .... a[left] ....
qs(s,left-1);
qs(left+1,e);
}
*/
#include <stdio.h>//1452 : 데이터 정렬 (large)
int a[100001]={};
void temp(int x,int y)
{
int t;
t = a[x];
a[x] = a[y];
a[y] = t;
}
void f(int s, int e)
{
int pivot=s; //s이외에 원하는 친구를 pivot으로 설정해도 OK
int i,j,left=s+1,right=e;
if(s==e){
return ;
}
for(i=0; ; i++){
for(j=left; j<=e; j++){ //left
if(a[pivot]<a[j]){
left=j;
break;
}
}
for(j=right; j>=s+1; j--){ //right
if(a[pivot]>a[j]){
right=j;
break;
}
}
if(left>=right){
break;
}
temp(left,right);
}
temp(right,pivot);
f(s,left-1);
f(left+1,e);
}
int main()
{
int i,j,n;
scanf("%d",&n);
for(i=1; i<=n; i++){
scanf("%d",&a[i]);
}
f(1,n);
printf("\n");
for(i=1; i<=n; i++){
printf("%d\n",a[i]);
}
return 0;
}