题目描述

给出一个 $1$ 到 $N$ 的全排列，要求选出一个尽可能长的子序列，满足：

1. 不存在两个数 $0\le 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$，意义见题目描述。

第二行包含 $N$ 个整数，表示给定的全排列。

输出格式

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

4
1 3 2 4

3

4
1 4 2 3

4

样例说明

第一个样例把 $3$ 去掉以后就合法了。

第二个样例没有冲突，直接输出 $4$。

数据规模与约定

对于 $100\%$ 的数据，保证 $1\le N\le 2\times 10^5$。

题目来源

ACM ICPC 2014-2015, NorthEastern European Regional Contest, Problem I