[Spoj 2371]Another Longest Increasing

给定一个由 $N$ 个数对 $(x_i,y_i)$ 组成的序列。请从中选出一个保持原有顺序的最长子序列，使得对于该子序列中的任意两个数对 $(x_i,y_i)$ 和 $(x_j,y_j)$，若 $i<j$，则同时满足 $x_i<x_j$ 且 $y_i<y_j$。

求满足条件的最长子序列长度。

输入格式

第一行输入一个整数 $N$，表示数对的数量。

接下来 $N$ 行，每行输入两个整数 $x_i$ 和 $y_i$，表示第 $i$ 个数对。

输出格式

输出一个整数，表示最长上升子序列的长度。

样例输入

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

样例输出

3

数据范围

• $N\le 10^5$。

来源与许可

本题为 SPOJ 2371「Another Longest Increasing」，题面与测试数据整理自 BZOJ 2225。

样例 1

输入

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

输出

3