题目描述

给定 $n$ 个元素的有序序列，每个元素有两个属性 $a_i,b_i$ 。

请输出这个序列的最长上升子序列的长度 。

最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，子序列相邻两个两个数两个维度属性严格递增，即 $a_i<a_{i+1},b_i<b_{i+1}$ 。

输入格式

第一行一个整数 $n$

接下来 $n$ , 第 $i+1$ 行两个整数表示 $a_i$ 和 $b_i$

输出格式

一个整数，表示答案

5
1 2
3 4
2 2
3 5
4 5

3

数据规模与约定

$n\le 10^5 ,a_i ,b_i\le 10^9$

$Subtask1$: $n\le 10^3 , a_i,b_i \le 10^9$, $20$ 分

$Subtask2$: $n\le 10^5, a_i,b_i \le 10^5$, $60$ 分

$Subtask3$: $n\le 10^5, a_i,b_i \le 10^9$, $20$ 分