Hide

Problem D
Kodama Hierarchy

/problems/kodamahierarchy/file/statement/en/img-0001.png
A group of kodama

You are currently trying to recruit a squad of kodama in order to take over the world.

You can pick some subset of $N$ kodamas as your group. The $i$-th kodama has a level of charisma $c_i$ and a level of aura $a_i$. Both $c_i$ and $a_i$ are nonnegative.

Kodamas operate under a hierarchical system. This means that kodamas are only satisfied in a group if every other kodama in the group is strictly lower or strictly higher in both aura and charisma. In other words, no two kodamas can exist in the group if one kodama has higher aura and the other one has higher charisma, or if they are equal in either stat.

However, kodamas are also social creatures. If any non-empty subset of the other kodamas from the $N$ kodamas can be added to your group of kodamas, without removing any kodamas currently in the group, while still preserving the hierarchical rules, the kodamas will rattle at you, not allowing you to form the group.

Since kodamas are quite chaotic, you want to pick out the least kodamas possible for the group. Find the minimum number of kodamas you can form a valid group with.

Input

The first line contains a single integer $N \: (1 \leq N \leq 2 \cdot 10^5)$, representing the number of kodamas, followed by $N$ lines. Each of these lines contains 2 space separated integers $a_i \: (0 \leq a_i \leq 10^9) $ followed by $c_i \: (0 \leq c_i \leq 10^9) $, detailing the aura and charisma, respectively, of the $i$th kodama.

Output

Output one line containing a single integer, representing the minimum size of a valid kodama group that you can form.

Sample Input 1 Sample Output 1
5
2 0
0 32
7 10
4 88
5 47
2
Sample Input 2 Sample Output 2
6
6 3
13 11
7 10
10 15
9 5
2 5
3

Please log in to submit a solution to this problem

Log in