도미노 무너트리기
시간 제한1초메모리 제한1024 MB
도미노를 좌표 순으로 정렬한 뒤, 모든 도미노가 오른쪽으로 쓰러지도록 처음 밀어야 하는 최소 개수를 구한다.
문제
미야노는 개의 도미노를 가지고 놀고 있다. 각각의 도미노는 1차원 좌표계의 좌표 위에 위치하고 있고 길이를 가진다. 번째 도미노의 좌표를 , 길이를 라 하자. 도미노는 오른쪽으로 무너트릴 수 있다. 길이 를 가지는 도미노가 위치 에 있을 때 오른쪽으로 무너질 경우 좌표 값이 보다 크고 보다 작거나 같은 도미노 중 가장 작은 좌표를 가지는 도미노가 오른쪽으로 무너진다.
미야노는 도미노를 최소한의 횟수로 무너트려서 모든 도미노를 무너트리려고 한다. 머리가 나쁜 미야노는 최소한의 횟수를 구하지 못해 여러분에게 답을 물어봤다. 미야노를 위해 모든 도미노가 무너지려면 처음에 몇 개의 도미노를 무너트려야 하는지 구해주자.
입력
첫 번째 줄에 이 주어진다.
두 번째 줄부터 번째 줄 까지 가 공백으로 구분되어 주어진다.
어떤 두 도미노가 같은 좌표를 가지는 경우는 주어지지 않는다.
출력
모든 도미노가 무너지기 위해 미야노가 처음에 무너트려야 할 도미노의 갯수를 구해주자.