"Вкладені прямокутники"#6084
Розглянемо послідовність прямокутників a_1 \times b_1, a_2 \times b_2, , a_N \times b_N. Для кожного , a_j \leq b_j. Обертати прямокутники не можна.
Прямокутник a_i \times b_i можна вкласти всередину прямокутника a_k \times b_k лише якщо a_i < a_k та b_i < b_k.
Називаємо послідовність прямокутників вкладеною, якщо кожен з них знаходиться у наступному.
Знайдіть найбільшу вкладену підпослідовність, тобто найбільшу вкладену послідовність серед усіх можливих підпослідовностей заданої послідовності.
Перший рядок містить кількість прямокутників (1 \leq N \leq 100\ 000).
Кожен з наступних рядків містить два цілих числа a_i і b_i (1 \leq a_i \leq b_i \leq 10^9), розмір -го прямокутника.
Виведіть одне число — довжину найбільшої вкладеної підпослідовності.
Приклад 1