Forest

Interview

Time limit1sMemory limit128 MB

Summary

Count distinct species, since the thickest tree of each species could be the oldest.

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

Problem

In the forest of Byteotia, every tree is labeled and stored in a database. Unfortunately some of the records were damaged, so for each tree we now know only its trunk thickness and its species. When comparing two trees of the same species, the tree with the thicker trunk is always the older one. You may also assume that no two trees of the same species have the same trunk thickness.

Determine how many trees are candidates for the oldest tree in the forest. A tree is a candidate for the oldest tree if, based only on the available information, no other tree is guaranteed to be older than it, so it could be the oldest tree in the whole forest.

Input

The first line contains an integer $n$ ( $1 \le n \le 10^6$ ), the number of trees in the forest. Each of the next $n$ lines describes one tree with two integers $g$ and $r$ ( $1 \le g \le 10^9$ , $1 \le r \le 10^6$ ), the trunk thickness and the species of the tree, respectively.

Output

Print a single integer: the number of candidates for the oldest tree in the forest.

Examples1

Example 1
Input
```
4
3 1
4 1
5 2
2 3
```
Expected output
```
3
```