You’ve just finished writing a random array generator for
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.
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$.
Print the minimum possible maximum occurrence of a value of $A$ after exactly $K$ removal.
($10$ Points): $K = 0$, $N \leq 3\, 000$, $A[i] \leq 3\, 000$, and $A$ is sorted in non-decreasing order.
($10$ Points): $K = 0$, $N \leq 3\, 000$, and $A[i] \leq 3\, 000$.
($10$ Points): $K = 0$ and $N \leq 3\, 000$.
($20$ Points): $K = 0$.
($30$ Points): $N \leq 3\, 000$.
($20$ Points): No additional constraints.
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.
The I/O files are large. Please use fast I/O methods.
|Sample Input 1||Sample Output 1|
10 0 1 1 3 3 3 3 3 7 7 7
|Sample Input 2||Sample Output 2|
10 3 3 1 7 3 3 3 7 3 1 7