题目描述

给你一个长度为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$ 。

请你求出该序列长度最长的一个子序列，满足：

• 该序列是一个递增子序列
• 相邻元素差值为 $1$。

输出该最大长度。

输入格式

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

第二行输入 $n$ 个数字 $a_1,a_2,\ldots,a_n$。

输出格式

一个整数表示答案。

7
3 4 3 5 7 6 2

4

样例 1 解释

符合要求的子序列是 $(3,4,5,6)$。注意不能是 $(3,4,5,7)$。

5
5 4 3 2 1

1

10
1 2 3 4 5 6 7 8 9 10

10

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 2\times 10^5$，$1\leq a_i\leq 10^9$。

• 子任务 1（$30$ 分）：满足 $n\leq 20$。
• 子任务 2（$30$ 分）：满足 $n\leq 2000$。
• 子任务 3（$40$ 分）：无特殊限制。