/*
#include <stdio.h>
struct p
{
int number;
int gas;
};
int main()
{
struct p st [10001];
struct p temp;
int n,i,j;
scanf ("%d",&n);
for (i=1; i<=n; i++)
{
scanf ("%d %d",&st[i].number,&st[i].gas);
}
for (i=1; i<n; i++)
{
for (j=1; j<=n-1; j++)
{
if (st[j].number > st[j+1].number)
{
temp = st[j];
st[j] = st[j+1];
st[j+1] = temp;
}
}
}
for (i=1;i<=n;i++)
{
printf ("%d %d\n",st[i].number,st[i].gas);
}
return 0;
}
*/
/*
#include <stdio.h>
struct p
{
int math;
int information;
int count;
};
int main ()
{
struct p st[1001];
struct p temp;
int n,i,j,cnt=0;
scanf ("%d ",&n);
for (i=0; i<n; i++)
{
scanf ("%d %d",&st[i].math,&st[i].information);
st[i].count = i+1;
}
for (i=0; i<n; i++)
{
for (j=0; j<n-1; j++)
{
if (st[j].math < st[j+1].math)
{
temp = st[j];
st[j] = st[j+1];
st[j+1] = temp;
}
}
if (st[j].math=st[j+1].math)
{
st[j].information;
}
}
for (i=0; i< n; i++)
{
printf ("%d %d %d\n",st[i].count,st[i].math,st[i].information);
}
return 0;
}
*/
/*
#include <stdio.h>
int partition (int arr[],int left, int right)
{
int temp;
int pivot=left;
while (arr[pivot]>=arr[left])
{
left++;
}
while (arr[pivot] < arr[right])
{
right --;
}
if (left <= right)
{
temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
return right;
}
void quick_sort(int arr[],int left,int right)
{
int pivot = partition (arr,left,right);
quick_sort(arr,left,right-1);
quick_sort (arr,left+1,right);
}
int main ()
{
int n,i,j,arr[9]= {0,20,18,50,40,9,19,5,25};
//scanf("%d",&n);
for (i=1;i<8;i++)
{
printf("%d ",arr[i]);
}
printf ("\n");
quick_sort (arr,1,8);
for (i=1;i<8;i++)
{
printf("%d ",arr[i]);
}
printf ("\n");
return 0;
}
*/