Swords

Interview

Time limit1sMemory limit1024 MB

Summary

Count the swords that no other sword matches or beats in both attack and defence.

Level: Easy3 of 10
Topics: Sorting, Array
Solved: No attempts yet

Problem

Yan Hao has $n$ swords numbered from 1 to $n$ . Sword $i$ has attack $a_i$ and defence $b_i$ .

Yan Hao considers sword $i$ useless if there is a different sword $j$ ( $j \ne i$ ) such that $a_i \le a_j$ and $b_i \le b_j$ . In other words, sword $i$ is useless when another sword matches or beats it in both attack and defence. A sword that is not useless is useful.

Two swords are equivalent if they have the same attack and the same defence. No two swords are equivalent.

Find the number of useful swords.

Input

The first line contains one integer $n$ .

Each of the next $n$ lines contains two space-separated integers. The $i$ -th of these lines contains $a_i$ and $b_i$ , the attack and defence of sword $i$ .

Output

Print one integer, the number of useful swords.

Constraints

$1 \le n \le 100\,000$
$1 \le a_i, b_i \le 10^9$
For all $1 \le i < j \le n$ , $a_i \ne a_j$ or $b_i \ne b_j$ .

Examples2

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