Задачи
"Вложенные прямоугольники"
"Вложенные прямоугольники"
Рассмотрим последовательность прямоугольников \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