样例下载

【题目描述】

Farmer John 的 $N$ 头奶牛排成一排，左数第 $i$ 头奶牛的身高为 $H_i$。已知奶牛的身高均为不大于 $N$ 的正整数。

Farmer John 要从中选取若干头奶牛参加合唱比赛。他希望满足：

1、选出的奶牛在原队伍中的位置是连续的一段；

2、选出的奶牛中有一头奶牛的身高恰好为 $1$。

3、选出的奶牛按身高从低到高排序后，任意两头相邻奶牛的身高相差恰好为 $1$。

问：John 最多能选出多少头奶牛？

【输入格式】

第一行：一个整数 $N$；

接下来一行：$N$ 个整数 $H_i$，数之间以单个空格隔开。数据保证至少存在一头奶牛的身高为 $1$。

【输出格式】

一个整数，表示答案。

【样例1输入】

3
3 1 3

【样例1输出】

1

【样例1解释】

只能选择身高为 $1$ 的一头奶牛。

【样例2输入】

7
5 2 1 3 2 4 6

【样例2输出】

4

【样例2解释】

最多可以选出 $4$ 头奶牛，如下划线所示：

5 2 1 3 2 4 6

【数据范围】

5% 的数据：$1 ≤ N ≤ 10$

10% 的数据：$1 ≤ N ≤ 10^3$

25% 的数据：$1 ≤ N ≤ 10^4$

45% 的数据：$1 ≤ N ≤ 10^5$

80% 的数据：$1 ≤ N ≤ 10^6$

100% 的数据：$1 ≤ N ≤ 10^7，1 ≤ H_i ≤ N$。