문제
다행히도, 염소들은 자유를 얻을 기회가 생겼다. 야생 염소가 지나가다가 그들을 발견한 것이다! 야생 염소는 날카로운 앞니를 가지고 있기에 남북 방향으로 빠르게 달려 서쪽에서부터 거리에 위치해 있는 밧줄을 모두 끊어버릴 수 있다. 단, 야생 염소의 체력에는 한계가 있기에 최소한의 횟수로 질주하고 싶다. 야생 염소가 질주하며 밧줄을 자르는 위치는 연속한 두 정수 좌표 사이의 중간에 위치하는 것이 가능하며, 해당 위치에 존재하는 모든 밧줄을 자르는 것이 가능하다.
각 밧줄의 길이와 그 말뚝의 위치가 주어질 때, 모든 염소들을 밧줄로부터 자유롭게 하려면 야생 염소가 최소한 몇 번의 자르기를 해야 하는지 구하는 프로그램을 작성하시오.
입력
첫 줄에 정수
[제약 조건]
1 \le N \le 500,000
출력
첫 줄에 모든 밧줄을 자르도록 하기 위한 최소 자르기 횟수를 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 20점 | |
| #2 | 30점 | 밧줄의 말뚝 위치와 밧줄의 길이가 모두 100 이하의 양의 정수로 주어진다. |
| #3 | 50점 | 추가 제한 없음 |
예제1
6
52
91
28
35
14
103
4
위 예제는 아래와 같은 모습이라 볼 수 있다.
1 1 1 1
1 2 3 4 5 6 7 8 9 0 1 2 3
-------------------------
. . . . 11111 . . . . . .
. . . . . . . . 222 . . .
. 333333333333333 . . . .
. . 44444444444 . . . . .
555555555 . . . . . . . .
. . . . . . . . . 6666666이 경우 야생 염소는 아래와 같은 네 위치에서 밧줄을 잘라 모든 염소를 자유롭게 만들어 줄 수 있다.
5.5의 위치에서 1, 3, 4번 밧줄을 자른다.
9.5의 위치에서 2번 밧줄을 자른다.
1.5의 위치에서 5번 밧줄을 자른다.
10.5의 위치에서 6번 밧줄을 자른다.