Задачі
"Вкладені прямокутники"
"Вкладені прямокутники"
Розглянемо послідовність прямокутників \textbf{a_1}×\textbf{b_1}, \textbf{a_2}×\textbf{b_2}, …, \textbf{a_N}×\textbf{b_N}. Для кожного \textbf{j}, \textbf{a}_\{j \}≤ \textbf{b_j}. Обертати прямокутники не можна. Прямокутник \textbf{a_i}×\textbf{b_i} можна вкласти всередину прямокутника \textbf{a_k}×\textbf{b_k} тільки якщо (\textbf{a}_\{i \}< \textbf{a_k}) та (\textbf{b}_\{i \}< \textbf{b_k}). Будемо називати послідовність прямокутників вкладеною, якщо кожен з них знаходиться у насиупному.
Напишіть програму, яка знайде найбільшу вкладену підпослідовність, тобто найбільшу вкладену послідовність серед усіх можливих пвдпослвдовностей заданої послідовності.
\InputFile
Перший рядок містить кількість прямокутників \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{100000}). Кожен з наступних \textbf{N} рядків містить два цілих числа \textbf{a_i b_i} (\textbf{1} ≤ \textbf{a}_\{i \}≤ \textbf{b}_\{i \}≤ \textbf{10^9}) - розмір \textbf{i}-го прямокутника.
\OutputFile
Вивести одне число - довжину найбільшої вкладеної підпослідовності.
Вхідні дані #1
5 10 10 3 7 5 5 4 9 12 12
Вихідні дані #1
3