Description

There are $n$ members in Coco's school's informatics team, and each person has a strength value $a_i$. The annual programming contest is coming, and the school has obtained several participation slots. The coach decides to divide the $n$ team members into several groups to participate in the contest.

However, no one wants to team up with someone whose strength differs too much from their own, so each group must consist of members whose strength values form a consecutive sequence. Also, no two players in the same group may have the same strength value. For example: $[1, 2, 3, 4, 5]$ is a valid grouping because the strengths are consecutive; $[1, 2, 3, 5]$ is not valid because the strengths are not consecutive; $[0, 1, 1, 2]$ is also not valid because two players have the same strength value $1$.

If a group is too small, it will not have enough time to score well. Therefore, Coco wants you to give a valid grouping that assigns everyone to exactly one group and maximizes the size of the smallest group. Output the maximum possible size of the smallest group.

Note: Strength values can be negative, and there is no limit on the number of groups.

Input Format

Two lines:

The first line contains a positive integer $n$, the number of team members.

The second line contains $n$ integers. The $i$-th integer $a_i$ denotes the strength of the $i$-th player.

Output Format

Output one line containing a single positive integer: the maximum possible size of the smallest group.

7
4 5 2 3 -4 -3 -5

3

Hint

Sample Explanation

Divide into $2$ groups: one group has strengths $[4, 5, 2, 3]$, and the other has $[-4, -3, -5]$. The smallest group size is $3$, and there is no better grouping than $3$.

Constraints

For $100\%$ of the testdata: $1 \leq n \leq 10^5$, $|a_i| \leq 10^9$.

This problem has $10$ test points, numbered $1 \sim 10$, each with additional guarantees as follows: | Test point ID | Constraints | | :-----------: | :-----------: | | $1 \sim 2$ | $n \leq 6$, $1 \leq a_i \leq 100$ | | $3 \sim 4$ | $n \leq 1000$, $1 \leq a_i \leq 10^5$ and $a_i$ are all distinct | | $5 \sim 6$ | $n \leq 10^5$, $a_i$ are all distinct | | $7 \sim 8$ | $n \leq 10^5$, $1 \leq a_i \leq 10^5$ | | $9 \sim 10$ | $n \leq 10^5$, $-10^9 \leq a_i \leq 10^9$ |

Translated by ChatGPT 5