摆动数列
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

给出n个有序二元组,第i个二元组表示为(x_i,y_i),现在需要从中选出最多的有序二元组。使得将这些二元组按顺序排列后,构成了摆动数列。
对于摆动数列的定义如下:
如果对于数列a中任意一个数字a_i都满足或者,则称这个数列为摆动数列。
如5,3,4,1,5,2就是一个合法的摆动数列。而5,4,4,2,3就不是一个合法的摆动数列。
需要注意的是,选出的这些二元组必须保持在原数列中的相对顺序。举个例子:如果原二元组序列为(2,1),(3,1),(2,4),(3,5),那么选出(2,4),(3,5)从而构成2,4,3,5就是一个合法的序列。而选出(3,1),(2,1)构成3,1,2,1则是不合法的,因为没有按照原来的顺序排列。选出(3,1),(2,4)构成3,1,2,4也是不合法的,因为这不是一个摆动数列。

输入描述:

第一行一个整数n,表示共有n个二元组
接下来n行,每行两个整数x,y。表示这n个二元组

输出描述:

一行一个整数。表示可以选出最多可以选出的二元组数目。
示例1

输入

复制
4
2 1
3 1
2 4
3 5

输出

复制
2

说明

选择{1,2}和选择{3,4}都是合法的方案。

备注:

对于前的数据,满足
对于前的数据,满足
对于另外的数据,满足
对于的数据,满足,