/*
3011**
#include <stdio.h>
int main()
{
int arr[10001];
int n,i,j,temp;
int flag=0; //확인할때 쓰는 flag
scanf("%d", &n);
for(i=1;i<=n;i++)
{
scanf("%d", &arr[i]);
}
for(i=1;i<n;i++)
{
flag=0;
for(j=1;j<=n-i;j++)
{
if(arr[j]>arr[j+1])
{
flag=1;
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
if(n==2&&arr[j]<arr[j+1])
{
printf("1");
break;
}
else if(flag==0)
{
printf("%d", i-1);
break;
}
}
return 0;
}
*/
/*
3017
#include <stdio.h>
typedef struct
{
int num;
int math;
int info;
}grade;
int main()
{
grade arr[1001],temp; //구조체가 달라서(?) temp가 int로 선언이 됬을때 arr를 담을 수 없음
int n,i,j,a=0;
scanf("%d", &n);
for(i=1;i<=n;i++)
{
a++;
scanf("%d %d", &arr[i].math,&arr[i].info);
arr[i].num=a;
}
for(i=1;i<n;i++)
{
for(j=1;j<=n-i;j++)
{
if(arr[j].math<arr[j+1].math)
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
else if(arr[j].math==arr[j+1].math)
{
if(arr[j].info<arr[j+1].info)
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
else if(arr[j].info==arr[j+1].info)
{
if(arr[j].num>arr[j+1].num)
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
}
for(i=1;i<=n;i++)
{
printf("%d %d %d\n",arr[i].num, arr[i].math,arr[i].info);
}
return 0;
}
*/
/*
1443
#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;j>=1 && a[j]>key;j--)
{
a[j+1]=a[j];
}
a[j+1]=key;
}
for (i=1; i<=n; i++)
printf("%d\n", a[i]);
return 0;
}
*/
/*
//<재귀함수>
//recursive
#include <stdio.h>
void rec(int n)
{
if(n==0) return ; //함수 종료
printf("%d\n",n);
rec(n-1); //나 자신을 호출
return ;
}
int main()
{
printf("hello\n");
rec(3);
printf("world");
return 0;
}
*/
/*
1901
#include <stdio.h>
void rec(int n)
{
if(n==0) return;
rec(n-1);
printf("%d\n", n);
return;
}
int main()
{
int n;
scanf("%d",&n);
rec(n);
return 0;
}
*/
/*
1902
#include <stdio.h>
void rec(int n)
{
if(n==0) return;
printf("%d\n", n);
rec(n-1);
return;
}
int main()
{
int n;
scanf("%d", &n);
rec(n);
return 0;
}
/*
1904(complex)
if(a%2==0)
{
rec(a+1,b);
}
else
{
printf("%d ", a);
rec(a+2,b);
}
*/
/*
1904**
#include <stdio.h>
void rec(int a, int b)
{
if(a>b) return;
if(a%2==1) printf("%d ",a);
rec(a+1,b);
}
int main()
{
int a,b;
scanf("%d %d", &a,&b);
rec(a,b);
return 0;
}
*/
/*
1905
rec(n)= 1~ n의 합
=1+2+3+ ...+n-1+n
=1~n-1의합 +n
=rec(n-1)+n
*/
/*
1905**
#include <stdio.h>
int rec(int n)
{
if(n==1) return 1;
return rec(n-1)+n;
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", rec(n));
return 0;
}
*/
/*
1912*
#include <stdio.h>
int rec(int n)
{
if(n==1) return 1;
return rec(n-1)*n;
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", rec(n));
return 0;
}
*/
/*
1915**
//fib(n) == n번째 피보나치수
#include <stdio.h>
int fib(int n)
{
if(n==1||n==2) return 1;
return fib(n-1)+fib(n-2);
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", fib(n));
return 0;
}
*/
/*
1916
#include <stdio.h>
int memo[201]={}; //이미 한번 구해진 수 는 memo에 저장
int fib(int n)
{
if(memo[n]!=0) return memo[n];
if(n==1||n==2) return memo[n]=1;
return memo[n]=(fib(n-1)+fib(n-2))%10009;
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", fib(n));
return 0;
}
*/