题目描述

给定 $N$ 个数对 $(x_i, y_i)$，求最长上升子序列的长度。上升序列定义为 $\{(x_i, y_i)\}$ 满足对 $i\lt j$ 有 $x_i\lt x_j$ 且 $y_i\lt y_j$。

输入格式

第一行一个整数 $n$，接下来 $n$ 行，每行两个整数 $x_i,y_i$。

输出格式

8 
1 3 
3 2 
1 1 
4 5 
6 3 
9 9 
8 7 
7 6

3

提示

$2\le n \le 10^5,-10^9\le x_i,y_i\le 10^9$

题目来源

没有写明来源