Entry Records

Interview

Time limit1sMemory limit1024 MB

Summary

Given today's ordered entry and exit records, find the fewest records that must be missing so each person's enter and leave events alternate correctly.

Level: Easy3 of 10
Topics: Hash map, Implementation
Solved: No attempts yet

Problem

A military police officer at a guard post finished the day shift and went through today's entry records for a security check. He realized that some of today's entry records are missing.

Today's entry records total $N$ , and the records are always written in the order in which people entered or left.

The $i$ -th entry record is written as two integers $a_i$ and $b_i$ . $a_i$ is the number of the person entering or leaving. If $b_i$ is $1$ , the person entered the base. If $b_i$ is $0$ , the person left the base. Before the first record and after the last record, nobody was inside the base.

Using today's entry records, find the minimum number of missing entry records over the whole day.

Input

The first line contains the number of entry records $N$ . ( $1 \leq N \leq 200\,000$ )

From the second line through line $N+1$ , the $i$ -th entry record is given as the integers $a_i$ and $b_i$ , separated by a space. ( $1 \leq a_i \leq 200\,000$ , $0 \leq b_i \leq 1$ )

Output

Print the minimum number of entry records that were missing during the day.

Examples2

Example 1
Input
```
8
1 1
2 1
1 1
4 1
3 0
5 1
4 0
1 0
```
Expected output
```
4
```
Example 2
Input
```
4
100 1
345 1
345 0
100 0
```
Expected output
```
0
```