求可重排数组的最长连续段子数组长度

时间限制：1.0 s 内存限制：512.0 MB

题目描述

对于$k$个整数构成的数组$[b_1,b_2\dots b_k]$，如果对$1<=i<k$都有$b_{i+1}=b_i+1$，那么称数组$b$是一个连续段。 给定由$n$个整数构成的数组$[a_1,a_2\dots a_n]$，你可以任意重排数组$a$中元素顺序。请问在重排顺序之后，$a$所有是连续段的子数组中，最长的子数组长度是多少？

样例说明

对于数组$[1,0,2,4]$，可以将其重排为$[4,0,1,2]$，共有10个子数组：$[4],[0],[1],[2],[4,0],[0,1],[1,2],[4,0,1],[0,1,2],[4,0,1,2]$。其中除$[4,0],[4,0,1],[4,0,1,2]$以外的子数组均是连续段，因此最长连续段子数组长度为3。

输入格式

第一行，一个正整数$n$，表示数组长度。 第二行，$n$个整数$a_1,a_2\dots a_n$，表示数组中的整数。

输出格式

一行，一个整数，表示数组$a$重排顺序后，所有是连续段的子数组的最长长度。

样例

输入样例1

4
4 0 1 2

输出样例1

3

输入样例2

9
9 9 8 2 4 4 3 5 3

输出样例2

4

数据范围

• 40%的测试点：$1 \le n \le 8$
• 所有测试点：$1 \le n \le 10^5$, $-10^9 \le a_i \le 10^9$