Time Limit : sec, Memory Limit : KB
English / Japanese  

Voting

Problem Statement

At JOI High School, a vote was held on a certain proposal, asking students to vote either "for" or "against." N students voted in order. Before voting, each student could know how the other students who had already voted had voted.

The i-th student (1 ≦ i ≦ N) voted "for" if the following condition was satisfied, and voted "against" otherwise.

  • Among the Xi students who voted immediately before, that is, the students who voted i - 1, i - 2, ..., i - Xi-th, at least Yi voted "for."

Note that if Yi = 0, the student voted "for" regardless of the other students' votes, and if Yi = Xi + 1, the student voted "against" regardless of the other students' votes.

Given the information about each student's voting rule, write a program to find the number of students who voted "for."

Constraints

  • 1 ≦ N ≦ 500 000.
  • 0 ≦ Xi ≦ i - 1 (1 ≦ i ≦ N).
  • 0 ≦ Yi ≦ Xi + 1 (1 ≦ i ≦ N).
  • All input values are integers.

Input

The input is given from standard input in the following format.
N
X1 Y1
X2 Y2
:
XN YN

Output

Output the number of students who voted "for" in one line to standard output.

Sample Input and Output

Sample Input 1

4
0 1
1 0
1 1
3 3

Sample Output 1

2

The votes were cast in order by 4 students as follows.

  1. The 1st student voted "against" because Y1 = X1 + 1.
  2. The 2nd student voted "for" because Y2 = 0.
  3. Among the X3 (= 1) student who voted immediately before, 1 voted "for," which is at least Y3 (= 1). Therefore, the 3rd student voted "for."
  4. Among the X4 (= 3) students who voted immediately before, 2 voted "for," which is not at least Y4 (= 3). Therefore, the 4th student voted "against."

There are 2 students who voted "for." Therefore, output 2.

Sample Input 2

5
0 0
1 1
2 3
3 1
4 3

Sample Output 2

4

Sample Input 3

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

Sample Output 3

4

Creative Commons License

Japan Information Olympiad Committee "Japan Information Olympiad 2nd Women's Division Finals Problem"