Məsələlər
"Nested rectangles"
"Nested rectangles"
Let’s consider a sequence of rectangles \textbf{a_1}×\textbf{b_1}, \textbf{a_2}×\textbf{b_2}, …, \textbf{a_N}×\textbf{b_N}. For each \textbf{j}, \textbf{a}_\{j \}≤ \textbf{b_j}. Rectangles cannot be rotated. Rectangle \textbf{a_i}×\textbf{b_i} can be put inside rectangle \textbf{a_k}×\textbf{b_k} iff (\textbf{a}_\{i \}< \textbf{a_k}) and (\textbf{b}_\{i \}< \textbf{b_k}). We call sequence of rectangles nesting sequence, iff each rectangle can be put inside following one.
Your task is to write a program that finds the longest nesting subsequence, i. e. the longest nesting sequence among all subsequences of the given sequence.
\InputFile
The \textbf{1^st} line of input data contains the number of rectangles \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{100000}). Each of the following \textbf{N} lines contains two integers \textbf{a_i b_i} (\textbf{1} ≤ \textbf{a}_\{i \}≤ \textbf{b}_\{i \}≤ \textbf{10^9}) --- size of \textbf{i}-th rectangle.
\OutputFile
Output exactly one integer number --- the length of the longest nesting subsequence.
Giriş verilənləri #1
5 10 10 3 7 5 5 4 9 12 12
Çıxış verilənləri #1
3