소 떼 질주
시간 제한1초메모리 제한256 MB
y축 양의 방향을 가로지르는 동안 한 번이라도 가장 앞에 보이는 소를 셉니다.
문제
농부 존이 기르는 소 마리()가 농장 앞 도로를 우르르 달려간다. 사실은 어느 소가 가장 빠른지 겨루는 달리기 경주다.
위에서 내려다보면 소 한 마리는 길이가 1인 수평 선분이고, 에서의 왼쪽 끝점 좌표로 위치를 나타낸다. 예를 들어 은 에 에서 까지 이어지는 선분인 소다. 모든 소는 오른쪽( 방향)으로 달리고, 속도는 오른쪽으로 1만큼 가는 데 걸리는 시간을 정수로 준다.
존은 소가 외양간에서 우유를 만들지 않고 밖에서 달리는 것이 못마땅해서, 경주가 끝나면 따끔하게 훈계하려고 한다. 어느 소가 경주에 참가했는지 알아내려고 존은 에 서서 방향으로 뻗은 반직선을 바라본다. 경주가 진행되는 동안 한 번이라도 이 반직선에서 가장 먼저 보이는 소가 되면, 존은 그 소를 본 것이다. 어떤 소는 존의 시선을 지나는 동안 계속 다른 소가 앞에 있어서 보이지 않을 수 있다.
경주 내내 존이 볼 수 있는 소가 몇 마리인지 구하라.
입력
첫째 줄에 이 주어진다.
다음 개 줄에 소 한 마리를 나타내는 정수 , , 이 공백으로 구분되어 주어진다. 그 소는 에 왼쪽 끝점이 이고, 시간 마다 거리 1씩 일정한 속도로 오른쪽으로 이동한다. 는 , 는 이며, 충돌이 생기지 않도록 모든 소의 는 서로 다르다. 은 이다.
출력
부터 경주가 끝날 때까지 존이 볼 수 있는 소의 수를 정수 하나로 출력한다.
힌트
시간은 이후로 연속해서 흐른다. 어떤 소가 반직선 위에 있는 시각 가운데 자기보다 가 작은 소가 같은 시각에 그 반직선 위에 없는 시각이 하나라도 있으면, 존은 그 소를 본다.
소의 선분은 양 끝점을 포함한다. 따라서 오른쪽 끝점이 에 닿는 순간부터 왼쪽 끝점이 을 지나는 순간까지가 그 소가 존의 시선 위에 있는 시간이다.