Longest Consecutive Segment

Problem Description

For an array $[b_1, b_2, \ldots, b_k]$ of $k$ integers, if $b_{i+1} = b_i + 1$ holds for all $1 \le i < k$, then we call the array $b$ a consecutive segment.

You are given an array $[a_1, a_2, \ldots, a_n]$ of $n$ integers. You may rearrange the elements of $a$ in any order. After rearranging, among all subarrays of $a$ that are consecutive segments, what is the length of the longest one?

For example, for the array $[1, 0, 2, 4]$, it can be rearranged as $[4, 0, 1, 2]$, which has the following $10$ subarrays: $[4], [0], [1], [2], [4, 0], [0, 1], [1, 2], [4, 0, 1], [0, 1, 2], [4, 0, 1, 2]$. Among them, all except $[4, 0], [4, 0, 1], [4, 0, 1, 2]$ are consecutive segments, so the longest subarray that is a consecutive segment has length $3$.

Input Format

The first line contains a positive integer $n$, the length of the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$, the elements of the array.

Output Format

One line containing one integer: the length of the longest subarray that is a consecutive segment after rearranging $a$.

Sample Input 1

4
1 0 2 4

Sample Input 2

9
9 9 8 2 4 4 3 5 3

Sample Output 1

3

Sample Output 2

4

Sample Explanation

For the first sample, one possible rearrangement of $[1, 0, 2, 4]$ is $[4, 0, 1, 2]$. In this permutation the subarray $[0, 1, 2]$ satisfies that each number is exactly $1$ greater than the previous, so it is a consecutive segment of length $3$. It can also be arranged as $[0, 1, 2, 4]$, where the consecutive segment $[0, 1, 2]$ of length $3$ still exists. No consecutive segment longer than $3$ can be obtained, so the answer is $3$.

Constraints

For $40\%$ of the test cases, $1 \le n \le 8$ is guaranteed.

For all test cases, $1 \le n \le 10^5$ and $-10^9 \le a_i \le 10^9$ are guaranteed.