投票 (Voting)

問題文

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

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

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

ただし， Y_i = 0 のときは他の生徒の投票に関わらず「賛成」に投票し，Y_i = X_i + 1 のときは他の生徒の投票に関わらず「反対」に投票したとする．

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

制約

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

入力

入力は以下の形式で標準入力から与えられる．
N
X₁ Y₁
X₂ Y₂
:
X_N Y_N

出力

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

入出力例

入力例 1

4
0 1
1 0
1 1
3 3

出力例 1

2

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

1. 1 番目に投票した生徒は，Y₁ = X₁ + 1 であるため，「反対」に投票した．
2. 2 番目に投票した生徒は，Y₂ = 0 であるため，「賛成」に投票した．
3. 直前に投票した X₃ (= 1) 人の生徒のうち「賛成」に投票したのは 1 人で，これは Y₃ (= 1) 人以上である．そのため，3 番目に投票した生徒は「賛成」に投票した．
4. 直前に投票した X₄ (= 3) 人の生徒のうち「賛成」に投票したのは 2 人で，これは Y₄ (= 3) 人以上ではない．そのため，4 番目に投票した生徒は「反対」に投票した．

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

入力例 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

---