2225 - [Spoj 2371]Another Longest Increasing 

   给定N个数对(xi, yi)，求最长上升子序列的长度。上升序列定义为{(xi, yi)}满足对i<j有xi<xj且yi<yj。

Input

Output

Examples

Input

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

Output

3

Hint

数据范围100000

时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题