시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 1024 MB140937783.696%

문제

JOI 高校において,ある議題に関して「賛成」か「反対」かを問う採決が行われ,N 人の生徒が順番に投票を行った.生徒は自分の投票前に,それまでに投票した他の生徒がどちらに投票したかを知ることができた.

i 番目 (1 ≦ i ≦ N) に投票した生徒は,次の条件を満たしたとき「賛成」に投票し,満たさなかったとき「反対」に投票した.

  • 直前に投票した Xi 人の生徒,すなわち i - 1, i - 2, ..., i - Xi 番目に投票した生徒のうち,Yi 人以上が「賛成」に投票した.

ただし, Yi = 0 のときは他の生徒の投票に関わらず「賛成」に投票し,Yi = Xi + 1 のときは他の生徒の投票に関わらず「反対」に投票したとする.

各生徒の投票についての情報が与えられたとき,「賛成」に投票した生徒の人数を求めるプログラムを作成せよ.

입력

入力は以下の形式で標準入力から与えられる.

N
X1 Y1
X2 Y2
:
XN YN

출력

標準出力に,「賛成」に投票した生徒の人数を 1 行で出力せよ.

제한

  • 1 ≦ N ≦ 500 000.
  • 0 ≦ Xi ≦ i - 1 (1 ≦ i ≦ N).
  • 0 ≦ Yi ≦ Xi + 1 (1 ≦ i ≦ N).
  • 入力される値はすべて整数である.

서브태스크

번호배점제한
128

N ≦ 3 000.

232

Xi = i - 1 (1 ≦ i ≦ N).

340

追加の制約はない.

예제 입력 1

4
0 1
1 0
1 1
3 3

예제 출력 1

2

投票は,以下のように 4 人の生徒によって順番に行われた.

  1. 1 番目に投票した生徒は,Y1 = X1 + 1 であるため,「反対」に投票した.
  2. 2 番目に投票した生徒は,Y2 = 0 であるため,「賛成」に投票した.
  3. 直前に投票した X3 (= 1) 人の生徒のうち「賛成」に投票したのは 1 人で,これは Y3 (= 1) 人以上である.そのため,3 番目に投票した生徒は「賛成」に投票した.
  4. 直前に投票した X4 (= 3) 人の生徒のうち「賛成」に投票したのは 2 人で,これは Y4 (= 3) 人以上ではない.そのため,4 番目に投票した生徒は「反対」に投票した.

「賛成」に投票した生徒は 2 人である.したがって,2 を出力する.

この入力例は小課題 1,3 の制約を満たす.

예제 입력 2

5
0 0
1 1
2 3
3 1
4 3

예제 출력 2

4

この入力例はすべての小課題の制約を満たす.

예제 입력 3

10
0 0
1 2
1 1
1 0
3 1
2 3
1 1
5 3
8 4
7 2


예제 출력 3

4

この入力例は小課題 1,3 の制約を満たす.

채점 및 기타 정보

  • 예제는 채점하지 않는다.