/*
1452*****
#include <stdio.h>
int arr[100001]={};
void swap(int a, int b)
{
int t=arr[a];
arr[a]=arr[b];
arr[b]=t;
}
void quick_sort(int s, int e)
{
int pivot=s;
int low=s, high=e+1;
if(s>=e) return; //여기*
do
{
do
{
low++;
}while(arr[low]<arr[pivot]);
do
{
high--;
}while(arr[high]>arr[pivot]);
if(low<high) swap(low,high);
}while(low<high);
swap(pivot,high);
quick_sort(s,high-1);
quick_sort(high+1,e);
}
int main()
{
int n,i;
scanf("%d", &n);
for(i=1;i<=n;i++)
{
scanf("%d", &arr[i]);
}
quick_sort(1,n);
for(i=1;i<=n;i++)
{
printf("%d\n", arr[i]);
}
return 0;
}
*/
/*
//선입선출(FIFO) <Queue>
#include <stdio.h>
#define SIZE 5
int circular_queue[SIZE];
int front=0; //data가 마지막으로 나간 위치
int rear=0; //data가 마지막으로 들어온 위치
void enqueue(int data) //stack에서의 push와 비슷
{
if((rear+1)%SIZE==front)
{
printf("queue is full!!\n");
return ; //FULL
}
rear=(rear+1)%SIZE;
circular_queue[rear]=data;
}
int dequeue() //stack에서의 pop과 비슷
{
int tmp;
if(front==rear)
{
printf("queue is empty!!\n");
return -1; //empty
}
front=(front+1)%SIZE;
tmp=circular_queue[front];
circular_queue[front]=0;
return tmp;
}
void view()
{
printf("circular queue : ");
for(int i=0; i<SIZE; i++)
{
printf("%d ",circular_queue[i]);
}
printf("\nfront : %d rear : %d\n\n",front,rear);
}
int main()
{
int a, b, c;
while(1)
{
printf("1. enqueue 2.dequeue >> ");
scanf("%d",&a);
if(a==1)
{
printf("enq data >> ");
scanf("%d",&b);
enqueue(b);
view();
}
else if(a==2)
{
printf("deq data >> ");
b=dequeue();
if(b!=-1) printf("%d\n",b);
view();
}
else
return 0;
}
}
*/
/*
//<Binary Search(이분 탐색)>
#include <stdio.h>
int arr[101]={},a;
int binary_search(int s,int e)
{
int mid=(s+e)/2;
if(s>e) return -1;
if(arr[mid]==a) return mid;
else if(arr[mid]>a) binary_search(s,mid-1);
else if(arr[mid]<a) binary_search(mid+1,e);
}
int main()
{
int n,i;
scanf("%d", &n);
scanf("%d", &a);
for(i=1;i<=n;i++)
{
scanf("%d", &arr[i]);
}
printf("%d", binary_search(1,n));
return 0;
}
*/
/*
3002
#include <stdio.h>
int arr[1000001]={},arrm[100001]={};
int binary_search(int s,int e,int a)
{
int mid=(s+e)/2;
if(s>e) return -1;
if(arr[mid]==a) return mid;
else if(arr[mid]>a) binary_search(s,mid-1,a);
else if(arr[mid]<a) binary_search(mid+1,e,a);
}
int main()
{
int n,m,i,a;
scanf("%d", &n);
for(i=1;i<=n;i++)
{
scanf("%d", &arr[i]);
}
scanf("%d", &m);
for(i=1;i<=m;i++)
{
scanf("%d", &arrm[i]);
a=arrm[i];
printf("%d ", binary_search(1,n,a));
}
return 0;
}
*/
/*
2633***
#include <stdio.h>
int arr[100001]={},k,n;
int binary_search(int s,int e)
{
int mid=(s+e)/2;
if(s==e)
{
if(arr[s]>=k) return s;
else return n+1;
}
if(arr[mid]>=k) binary_search(s,mid);
else if(arr[mid]<k) binary_search(mid+1,e);
}
int main()
{
scanf("%d %d", &n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d", &arr[i]);
}
printf("%d", binary_search(1,n));
return 0;
}
*/
/*
3004**
#include <stdio.h>
int arr[1000001]={},arrm[100001]={};
void swap(int a, int b)
{
int t=arrm[a];
arrm[a]=arrm[b];
arrm[b]=t;
}
void quick_sort(int s, int e)
{
int pivot=s;
int low=s, high=e+1;
if(s>=e) return ;
do
{
do
{
low++;
}while (arrm[low]<arrm[pivot]);
do
{
high--;
}while (arrm[high]>arrm[pivot]);
if(low<high) swap(low,high);
}while(low<high);
swap(pivot,high);
quick_sort(s,high-1);
quick_sort(high+1,e);
}
int binary_search(int s,int e,int a)
{
int mid=(s+e)/2;
if(s>e) return -1;
if(arrm[mid]==a) return mid;
else if(arrm[mid]>a) binary_search(s,mid-1,a);
else if(arrm[mid]<a) binary_search(mid+1,e,a);
}
int main()
{
int n,i,a;
scanf("%d", &n);
for(i=0;i<n;i++)
{
scanf("%d", &arr[i]);
arrm[i]=arr[i];
}
quick_sort(0,n-1);
for(i=0;i<n;i++)
{
a=arr[i];
printf("%d ", binary_search(0,n-1,a));
}
return 0;
}
*/