Nested rectangles#6084
Let us consider a sequence of rectangles a_1 \times b_1, a_2 \times b_2, , a_N \times b_N. For each , a_j \leq b_j. Rectangles cannot be rotated.
A rectangle a_i \times b_i can be placed inside a rectangle a_k \times b_k if and only if a_i < a_k and b_i < b_k.
We call a sequence of rectangles a nesting sequence if each rectangle can be placed inside the next one in the sequence.
Your task is to find the longest nesting subsequence, that is, the longest nesting sequence among all subsequences of the given sequence.
The first line contains the number of rectangles (1 \leq N \leq 100\ 000).
Each of the following lines contains two integers a_i and b_i (1 \leq a_i \leq b_i \leq 10^9), the sides of the -th rectangle.
Print a single integer, the length of the longest nesting subsequence.
Example 1