8114447 - [AHOI2018初中组]分组

小可可的学校信息组总共有n 个队员,每个人都有一个实力值a[i]a[i]。现在,一年一度的编程大赛就要到了,小可可的学校获得了若干个参赛名额,教练决定把学校信息组的nn 个队员分成若干个小组去参加这场比赛。

但是每个队员都不会愿意与实力跟自己过于悬殊的队员组队,于是要求分成的每个小组的队员实力值连续,同时,一个队不需要两个实力相同的选手。举个例子:[1, 2, 3, 4, 5][1,2,3,4,5]是合法的分组方案,因为实力值连续;[1, 2, 3, 5][1,2,3,5]不是合法的分组方案,因为实力值不连续;[0, 1, 1, 2][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≤100000,|a[i]|≤10^9。

本题共10 个测试点,编号为1~10,每个测试点额外保证如下:

1~2 n≤6, 1≤a[i]≤100
3~4 n≤1000, 1≤a[i]≤10^5n≤1000,且a[i]互不相同
5~6 n≤100000, a[i]互不相同
7~8 n≤100000, 1≤a[i]≤10^5
9~10 n≤100000, |a[i]|≤10^9

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题