投票 (Voting)

아직 제출이 없습니다시간 제한2초메모리 제한1024 MB

문제

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).
  • 入力される値はすべて整数である.