Problem G
Array Smoothening

You’ve just finished writing a random array generator for your competitive programming practical examination problem. However, when you tested it, you noticed that the distribution is skewed; some values may appear much more times than the other values. You wanted to smoothen the distribution, but you don’t want to modify your generator anymore. Thus, you decide to remove exactly $K$ elements from the array, such that the maximum occurrence of a value is minimized. Now, given an array $A$ of size $N$, determine the minimum possible maximum occurrence of a value from the array after you remove exactly $K$ elements from it.

Input

The first line contains two integers $N$ ($1 \leq N \leq 200\, 000$) and $K$ ($0 \leq K \leq N$).

The next line contains $N$ integers $A[i]$ ($1 \leq A[i] \leq 10^9$), the elements of the array $A$.

Output

Print the minimum possible maximum occurrence of a value of $A$ after exactly $K$ removal.

Subtasks

1. ($10$ Points): $K = 0$, $N \leq 3\, 000$, $A[i] \leq 3\, 000$, and $A$ is sorted in non-decreasing order.

2. ($10$ Points): $K = 0$, $N \leq 3\, 000$, and $A[i] \leq 3\, 000$.

3. ($10$ Points): $K = 0$ and $N \leq 3\, 000$.

4. ($20$ Points): $K = 0$.

5. ($30$ Points): $N \leq 3\, 000$.

6. ($20$ Points): No additional constraints.

Explanation

In the first sample, $1$ appears twice, $7$ appears three times, $3$ appears five times, and none of the elements will be removed. Thus, the maximum occurrence is five.

In the second sample, we can remove two occurrences of $3$ and one occurrence of $7$. Hence, $1$ and $7$ appear twice, and $3$ appears three times. Thus, the maximum occurrence is three.

Warning

The I/O files are large. Please use fast I/O methods.

10 0
1 1 3 3 3 3 3 7 7 7

5

10 3
3 1 7 3 3 3 7 3 1 7

3