Nested Dolls

Source: UVa

Version: Phuoc Hung OJ Extended

Problem Statement

Doll $(w_1,h_1)$ fits inside $(w_2,h_2)$ iff $w_1<w_2$ and $h_1<h_2$. Partition all dolls into the minimum number of nesting chains.

Input

The first line contains $m$. The second line contains $w_1,h_1,\ldots,w_m,h_m$.

Output

Print the minimum number of chains.

Subtasks

• Subtask 1 — 20%: $m\le100$.
• Subtask 2 — 30%: $m\le5000$.
• Subtask 3 — 50%: $m\le20000$, $1\le w_i,h_i\le10000$.

Example

Input

4
20 30 10 10 30 20 40 50

Output

2

Explanation

Two nesting chains are sufficient and one is impossible.