You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

探险协会总共有 $n$ 名探险家，每个人都有一个探险能力值 $a_i$。

现在，协会发现了若干个未知区域的探险机会，会长决定把 $n$名探险家分成若干个小组去探索这些区域。

但是每个探险家都不愿意与能力跟自己相差太大的同伴组队，于是要求分成的每个小组的成员能力值连续，同时，一个小组不需要两个能力相同的探险家。

举个例子：$[1,2,3,4,5]$ 是合法的分组方案，因为能力值连续；$[1,2,3,5]$ 不是合法的分组方案，因为能力值不连续；$[0,1,1,2]$ 同样不是合法的分组方案，因为出现了两个能力值为 1 的探险家。

但如果小组内人数太少，就会因为人手不足而无法应对复杂环境，于是会长想让你给出一个合法的分组方案，满足所有人都恰好分到一个小组，使得人数最少的组人数最多，输出人数最少的组人数的最大值。

注意：实力值可能是负数，分组的数量没有限制。

输入格式

输入有两行：

第一行一个正整数 n，表示队员数量。

第二行有 n 个整数，第 i 个整数 $a_i$ 表示第 i 个队员的实力。

输出格式

输出一行，包括一个正整数，表示人数最少的组的人数最大值。

样例

7
4 5 2 3 -4 -3 -5

3

说明提示

样例解释

分为 2 组，一组的队员实力值是 $[4,5,2,3]$，一组是 $[−4,−3,−5]$，其中最小的组人数为 $3$，可以发现没有比 $3$ 更优的分法了。

数据范围

$100$% 的数据满足：$1≤n≤10⁵$，$a_i≤10⁹$。