Maximize Minimum Group Size

There are n team members in the school information group, and each member has a strength value a_i (which may be negative). The school has obtained several participation slots in the annual programming contest. The coach decides to divide the n team members into several groups. However, no one is willing to team up with others whose strength differs too much – hence, in any group, the set of strength values (when sorted) must form a sequence of consecutive integers with no duplicates. For example, the group [1, 2, 3, 4, 5] is valid because the values are consecutive, while [1, 2, 3, 5] is not since 4 is missing; similarly, [0, 1, 1, 2] is invalid because the value 1 appears twice.

If a group has too few members, it might not have enough time to score high; therefore, the goal is to partition all members into valid groups such that the size of the smallest group is as large as possible. In other words, among all valid partitions (each member appears in exactly one group), find one in which the minimum group size is maximized, and output that maximum possible value.

Note: The strength values a_i may be negative, and there is no limit on the number of groups.

Mathematical formulation: Suppose you partition the multiset \(\{a_1, a_2,\dots, a_n\}\) into some groups \(G_1, G_2, \dots, G_k\) such that for each group \(G_j\), after sorting, if \(G_j = \{b_1, b_2, \dots, b_{\ell_j}\}\) then it must hold that \(b_{i+1} - b_i = 1\) for all \(1 \le i < \ell_j\) (and obviously all elements are distinct). Let \(L_j\) be the number of members in group \(G_j\). Our goal is to maximize \(\min_{1\le j\le k}L_j\).

inputFormat

The first line contains an integer n (\(1 \le n \le 10^5\)) representing the number of team members. The second line contains n space-separated integers a1, a2, ..., an (\(|a_i| \le 10^9\)), which are the strength values of the members.

outputFormat

Output a single integer, the maximum possible value of the minimum group size among all valid partitions.

sample

4
1 1 2 2

2