/*//1 3 7 7 7 7 7
#include <stdio.h>
int a[1000001]= {}, n;
int bs(int s, int e, int k) // a[s] ~ a[e] 에서 k값의 위치 리턴
{
int mid=(e+s)/2;
if(s==e)
{
if(a[mid]>=k)
{
return s;
}
return n+1;
}
if(a[mid]>=k)
bs(s,mid,k);
else
bs(mid+1, e, k);
}
int main()
{
int k;
scanf("%d %d", &n, &k);
for(int i=1;i<=n;i++)
{
scanf("%d", &a[i]);
}
printf("%d", bs(1, n, k));
return 0;
}
1452 : 퀵정렬 (재귀함수를 사용하는 새로운 정렬 기법)
3004 : 퀵정렬 + 이진탐색 (시간초과를 내지 않기 위해 )
3014 : 기존의 정렬 기법 x -> 메모이제이션을 사용해서 정렬처럼 작동하도록 만들기
*/
/*
#include <stdio.h>
int a[100001]={};
//quick_sort(int start, int end) // a[s] ~a[e] 정렬하세요
void qs(int s, int e)
{
int pivot=s,tmp;
if(s>=e) return; //길이가 1이거나 0일때 , 더이상 정렬할 원소가 없을때
int l=s;
int r=e+1;
do
{
do{
l++;
}while(a[pivot]>a[l]);
//a[l]은 a[pivot] 이상인 수
do{
r--;
}while(a[pivot]<a[r]);
// a[r]은 a[pivot]이하인 수
if(l<r){
tmp=a[l];
a[l]=a[r];
a[r]=tmp;
}
}while(l<r);
tmp=a[pivot];
a[pivot]=a[r];
a[r]=tmp;
qs(s,r-1);
qs(r+1,e);
}
int main()
{
int n, i;
scanf("%d", &n);
for(i=1;i<=n;i++)
{
scanf("%d", &a[i]);
}
qs(1, n);
for(i=1;i<=n;i++)
{
printf("%d\n", a[i]);
}
return 0;
}*/