/* 삽입정렬
#include <stdio.h>
int a[100001]= {};
int main()
{
int n, i, j, k;
scanf("%d", &n);
for(i=1; i<=n; i++)
{
scanf("%d", &a[i]);
}
for(i=2; i<=n; i++)
{
k=a[i];
for(j=i-1; a[j]>=k; j--)
if(a[j]>=k)
{
a[j+1]=a[j];
}
a[j+1]=k;
}
for(i=1; i<=n; i++)
{
printf("%d ", a[i]);
}
}
*/
/*1451
#include <stdio.h>
int main()
{
int i, n, j, k, a[10005]= {};
scanf("%d", &n);
for(i=0; i<n; i++)
{
scanf("%d", &a[i]);
}
for(i=1; i<n; i++)
{
for(j=0; j<n-i; j++)
{
if(a[j]>a[j+1])
{
k=a[j];
a[j]=a[j+1];
a[j+1]=k;
}
}
}
for(i=0; i<n; i++)
{
printf("%d\n", a[i]);
}
return 0;
}
*/
/*3011
#include <stdio.h>
int main()
{
int i, n, j, k, t, a[1005]= {};
scanf("%d", &n);
for(i=0; i<n; i++)
{
scanf("%d", &a[i]);
}
for(i=0; i<n; i++)
{
t=0;
for(j=0; j<n-1; j++)
{
if(a[j]>a[j+1])
{
t++;
k=a[j];
a[j]=a[j+1];
a[j+1]=k;
}
}
if(t==0)
{
printf("%d\n", i);
break;
}
}
return 0;
}
*/
/*
#include <stdio.h>
typedef struct _node
{
int a, b, rank;
} Node;
int main()
{
int n, i, j,q;
Node p[10001] = {};
Node k;
scanf("%d", &n);
for(i=0; i<n; i++)
{
scanf("%d %d", &p[i].a, &p[i].b);
p[i].rank=i+1;
}
for(i=0; i<n; i++)
{
for(j=0; j<n-1; j++)
{
if(p[j].a< p[j+1].a)
{
k=p[j];
p[j]=p[j+1];
p[j+1]=k;
}
}
}
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
{
if(p[j].a==p[j+1].a)
{
if(p[j].b< p[j+1].b)
{
k=p[j];
p[j]=p[j+1];
p[j+1]=k;
}
}
}
}
for(i=0; i<n; i++)
{
printf("%d %d %d\n", p[i].rank, p[i].a, p[i].b);
}
return 0;
}
*/
4012 3016