/*
// 3019 스케줄 정리
#include <stdio.h>
#include <string.h>
typedef struct
{
char name[100];
int date;
} schedule;
int main()
{
schedule arr[100];
int n,i,j,x,y,z;
schedule temp;
scanf("%d", &n);
for(i=1; i<=n; i++)
{
scanf("%s %d %d %d", arr[i].name,&x,&y,&z);
arr[i].date = x*10000 + y*100 + z;
}
for(i=1; i<n; i++)
{
for(j=1; j<=n-i; j++)
{
if(arr[j].date > arr[j+1].date)
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
else if(arr[j].date == arr[j+1].date)
{
if(strcmp(arr[j].name, arr[j+1].name)>0)
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
for(i=1; i<=n; i++)
{
printf("%s\n", arr[i].name);
}
return 0;
}
*/
/*
// 1452 데이터 정렬(large) - 퀵정렬
#include <stdio.h>
int arr[100000]= {};
void qsort(int s, int e)
{
if(s>=e) return ;
int p=s,temp;
int left=s, right=e+1;
do
{
do
{
left++;
}while(arr[p]>arr[left]);
do
{
right--;
}while(arr[p]<arr[right]);
if(left<right)
{
temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}while(left<right);
temp = arr[p];
arr[p] = arr[right];
arr[right] = temp;
qsort(s,right-1);
qsort(right+1,e);
}
int main()
{
int n,i,start,end;
scanf("%d",&n);
for(i=0; i<n; i++)
{
scanf("%d", &arr[i]);
}
start=0;
end=n-1;
qsort(start,end);
for(i=0; i<n; i++)
{
printf("%d\n",arr[i]);
}
return 0;
}
*/
// 3014 정렬을 빠르게 - 메모이제이션 이용하기
// 1093 이상한출석번호부르기1 참고
#include <stdio.h>
int main()
{
int n;
scanf("%d",&n);
int memo[10000]={};
}