제목: 사회적 거리두기 2

문제

농부 존은 세계적인 전염병인 소로나19 때문에 소들의 건강을 걱정하고 있다.

농부 존은 N마리의 소들에게 사회적 거리두기를 통해 병을 예방하고 있으나, 안타깝게도 이미 병에 걸린 소들이 존재한다. (1<=N<=1000). 소들은 1~N까지 번호가 부여되어 있고, 각 소들은 N번 칸에 배치되어있다. 존은 소들간에 병이 전염되는 최대 거리인 R이 존재한다는 사실을 알고 있다. 즉, R 거리 내에 병에 걸린 소가 있다면 다른 소도 전염이 되는 것이다.

하지만 안타깝게도 존은 R의 값을 모른다. 그러나 그는 어떤 소가 소로나19에 전염되었는지 알고 있다. 주어진 데이터를 통해서 처음 병에 걸린 소의 수의 최솟값을 출력하라.

입력 

첫 번째 줄에 소들의 수 N이 주어진다. 그 후 N줄에 소의 위치 x와 전염 여부 s가 주어진다. (0<=x<=10^6)
s가 0이면 건강한 소, 1이면 소로나19에 걸린 소이다. 적어도 한 마리의 소가 병에 걸릴 경우, 모든 소들은 병에 걸릴 가능성이 있다.

출력

처음 병에 걸린 소의 수의 최솟값을 출력하라.

힌트

예제를 보면 7번 위치의 소가 병에 걸렸는데 10번 위치의 소가 병에 걸리지 않은 것을 보면 R<3이라는 것을 알 수 있다. 따라서 (1, 3) 중에 하나, (6, 7) 중에 하나, (15) 번 소가 처음 병에 걸렸기에 최소 3마리의 소가 처음에 병에 걸렸음을 알 수 있다.