题目描述

一条直线上有 $n$ 个巡查点，从左到右编号为 $1,2,\ldots,n$。这些巡查点按照排列 $p_1,p_2,\ldots,p_n$ 的顺序依次开放。每个巡查点开放时，你需要当场决定是否巡查；未选的点不能在之后补选。

你可以从中选择若干个巡查点。形式化地，你需要选择一个满足 $1\le k\le n$ 的整数和一组下标 $1\le i_1<i_2<\cdots<i_k\le n$，并依次巡查

第一个巡查点可以任意选择。对于每个 $2\le j\le k$，必须存在某个 $1\le t<j$ 使得

也就是说，之后选择的每个巡查点，都必须在编号上与此前选择过的至少一个巡查点相邻。

请计算最多可以选择多少个巡查点。

输入格式

从文件 frontier.in 中读取数据。

第一行输入一个整数 $n$。

第二行输入 $n$ 个整数 $p_1,p_2,\ldots,p_n$，表示巡查点的开放顺序。

输出格式

输出到文件 frontier.out 中。

输出一个整数，表示最多可以选择的巡查点数量。

样例

1
1

1

5
3 1 4 2 5

4

样例解释

样例 #1 中，唯一的巡查点可以直接选择，因此答案为 $1$。

样例 #2 中，可以依次选择编号为 $3,4,2,5$ 的巡查点，它们在输入中的下标依次为 $1,3,4,5$。选择 $4$ 时它与 $3$ 相邻，选择 $2$ 时它与 $3$ 相邻，选择 $5$ 时它与 $4$ 相邻，因此可以选择 $4$ 个巡查点。如果选择全部 $5$ 个巡查点，第二个被选择的巡查点将是 $1$，它与此前唯一选择的 $3$ 不相邻，所以无法选择全部巡查点。故答案为 $4$。

数据规模与约定

对于所有数据，保证：

• $1\le n\le 200000$；
• 对于所有 $1\le i\le n$，$1\le p_i\le n$；
• $p_1,p_2,\ldots,p_n$ 是 $1,2,\ldots,n$ 的一个排列。

本题采用子任务捆绑计分。只有通过某个子任务内的所有测试点，才能获得该子任务的分数。各子任务独立计分。

下发文件

下载三组测试数据，非真实测试数据