题目描述

给定一个整数序列 $a_1,\dots,a_N$。你可以在序列中插入一个新元素（其值可以任意选择）。你的目标是最大化这样一个最长子序列的长度：该子序列中的值是连续整数。

这里的子序列可以由原序列中不连续的位置组成。

更形式化地说，设插入一个元素后的新序列为 $b_1,\dots,b_{N+1}$，我们希望找到最长的下标序列

使得对所有 $1\le j<k$，都有

输入格式

第一行输入一个整数 $N$，表示序列中的元素个数。

第二行输入 $N$ 个以空格分隔的整数，表示 $a_1,\dots,a_N$。

输出格式

输出一个整数，表示在最优插入一个元素之后，值为连续整数的最长子序列长度。

数据范围

• $1\le N\le 5\times 10^5$
• 对每个 $i$，有 $1\le a_i\le 5\times 10^5$

测试点

各测试点独立计分，按最佳解计分。

样例 #1

输入 #1

6
5 1 2 4 5 7

输出 #1

5

样例说明 #1

最优做法是在位置 $4$ 插入一个值为 $3$ 的元素，此时序列变为：

5 1 2 3 4 5 7

此时可以取到长度为 $5$ 的连续整数子序列。