7927: BZOJ3927：[Neerc2014]Improvements

给出一个1到N的全排列，要求选出一个尽可能长的子序列，满足 1：不存在两个数0<=i<j<N满足线段Min(A(i),A(i+1)),Max(A(i),A(i+1)) 和线段Min(A(j),A(j+1),Max(A(j),A(j+1))有交但不互相包含。 2：A(0)一直为0. 例如1 5 3 4和1 5 3 2是两个合法方案并且在后面加上任意一个数都将导致不合法。3 5 1不合法是因为[0,3]和[1,5]相交但不互相包含。 N<=200000

输入格式

如题

输出格式

如题

样例输入

input 1
4
1 3 2 4

input 2
4
1 4 2 3

样例输出

output 1
3

output 2
4

提示

第一个样例把3去掉以后就合法了 第二个样例没有冲突 直接输出4

题目来源

没有写明来源