黑暗爆炸OJ

DARKBZOJ

#1852. [MexicoOI06]最长不下降序列

Statistics 下载数据

Description

给你N对数A1,B1……An,Bn 。要求你从中找出最多的对，把它们按照一种方式排列，重新标号1,2,..,k。能满足对于每一对 i < j,都有 Ai > Bj。

Input

第一行给出一个数字N,N < = 100000 下面N行，分别给出Ai,Bi,其小于10^9

Output

输出K的极大值

Sample Input

4
3 12
10 20
21 13
10 2

Sample Output

3

Hint

Source