문제
조류독감(AI)으로 온 나라가 걱정에 쌓여 있는 와중에 이번에는 구제역이 발생했다는 뉴스가 흘러나왔다.
한우 목장을 운영하고 있는 우식이는 어떻게 하면 구제역 파동을 이겨낼 수 있을지 많은 고민을 하고 있다. 상태가 조금이라도 이상한 소가 있을 때에는 지체 없이 축사에서 제거하고 새로 영입된 소는 현재 있는 소들과 최대한 멀리 떨어지도록 배치하여 감염의 위험을 줄이려고 한다.
축사는 일렬로 길게 늘어져 있어서 각 단위당 한 마리씩 넣어서 기를 수 있게 되어 있고 1번부터 N번까지 번호가 붙어 있다.
처음에 들어온 소는 1번에 배치되고 두 번째 소는 1번에서 가장 멀리 떨어진 N번에 배치된다.
이후에 들어오는 소들은 현재 소들 중 가장 가까운 소와의 거리가 최대가 되는 위치에 배치하되 거리가 같은 경우에는 번호가 낮은 곳에 우선 배치되도록 한다.
예를 들어 크기가 10인 축사에 5마리를 차례대로 배치한다면 1, 10, 5, 3, 7번의 순서로 배치가 된다.
사육장의 크기와 소들의 정보를 입력 받아서 가장 마지막에 배치된 소의 사육장 위치를 출력하는 프로그램을 작성 하시오.
입력
첫 번째 줄에는 사육장의 크기 N과 소의 배치에 관한 정보의 수 M이 입력된다.(1 <= M <= N <= 100000)
두 번째 줄부터 M줄에 걸쳐 소의 배치에 관한 정보가 입력된다.
각 줄의 첫 번째에는 “IN” 또는 “OUT” 라는 문자열이 입력되는데 “IN”은 새로운 소를 사육장에 배치하라는 것이다. 소의 번호는 1번부터 입력되는 순서에 따라 차례대로 부여된다.
"OUT”이 입력되면 현재 사육장에 있는 소들의 번호 중 한 개의 번호를 추가로 입력 받아 해당하는 소를 사육장에서 제거한다.
출력
가장 마지막에 배치된 소의 위치를 출력한다.
예제
10 6
IN
IN
IN
IN
OUT 3
IN
6
출처
jungol
로그인해야 코드를 작성할 수 있어요.