//#include <stdio.h>
//#include <stdlib.h>
//
//int main()
//{
// printf("Hello world!\n");
// return 0;
//}
//S(k,n) => ( S(k-1,1)+ S(k=1,2)+ .....+S(k-1,n-1) ) +S(k-1,n)
// => S(k,n-1)+S(k-1,n)
//#include <stdio.h>
//
//int memo[15][15]= {};
//int S(int k,int n)
//{
// if(memo[k][n]!=0)
// return memo[k][n];
//
// if(k==0)
// return memo[k][n]=n;
//
// if(n==1)
// return memo[k][n]=1;
//
//
// return memo[k][n]=S(k,n-1)+S(k-1,n);
//
//}
//int main()
//{
// int n,k;
// while( scanf("%d%d", &k,&n) != EOF )
// printf("%d\n",S(k,n));
// return 0;
//}
//#include <stdio.h>
//
//void rec(int n)
//{
// if(n==0)
// return;
//
// printf("*");
// rec(n-1);
//}
//void tri(int n)
//{
// if(n==0)
// return ;
//
// tri(n-1);
// rec(n);
// printf("\n");
//}
//
//int main()
//{
// int n;
// scanf("%d",&n);
// tri(n);
// return 0;
//}
/*
#include <stdio.h>
int rec(int n)
{
if(n==0) return ;
rec(n/2);
printf("%d",n%2);
}
int main()
{
int n;
scanf("%d",&n);
// if(n==0) {
// printf("0");
// return 0;
// }
// rec(n);
if(n==0) printf("0");
else rec(n);
return 0;
}
*/
//#include <stdio.h>
//#define size 7
//
//int arr[size]= {5,7,3,10,2,1,9};
//
//void swap(int a, int b)
//{
// int tmp=arr[a];
// arr[a]=arr[b];
// arr[b]=tmp;
//}
//
//void quicksort(int start,int end)
//{
// int pivot = start;
// int low = start;
// int high = end;
//
// while(low<=high)
// {
// while(arr[pivot]>=arr[low] && low<=end)
// low++;
// while(arr[pivot]<=arr[high] &&high>=start)
// high--;
// if(low<=high)
// swap(low,high);
// }
//
// swap(pivot,high);
// if(start<high-1) quicksort(start,high-1);
// if(high+1<end) quicksort(high+1,end);
//}
//
//int main()
//{
//
// view();
// quicksort(0,size-1);
// view();
//}
//
//
//void view()
//{
// for(int i=0; i<size; i++)
// {
// printf("%d ",arr[i]);
// }
// printf("\n");
//}
/*
#include <stdio.h>
#define size 100000
int arr[size]= {};
void swap(int a,int b)
{
int tmp=arr[a];
arr[a]=arr[b];
arr[b]=tmp;
}
void quicksort(int start,int end)
{
int pivot=start;
int low=start;
int high=end;
while(low<=high)
{
while(arr[pivot]>=arr[low]&&low<=end)
low++;
while(arr[pivot]<=arr[high]&&high>=start)
high--;
if(low<=high)
swap(low,high);
}
swap(pivot,high);
if(start<high-1)
quicksort(start,high-1);
if(high+1<end)
quicksort(high+1,end);
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0; i<n; i++)
{
scanf("%d",&arr[i]);
}
if(n==1)
{
printf("%d",arr[0]);
return 0;
}
quicksort(0,n-1);
for(int i=0; i<n; i++)
{
printf("%d\n",arr[i]);
}
}
*/