We’re preparing your current view and syncing the latest data.
You are given an array and a number k. Your task is to remove exactly k elements from the array so that the number of distinct integers in the remaining array is minimized. Return the minimum possible number of distinct integers after these removals.
The first line contains two integers n and k — the size of the array and the number of elements to remove respectively. The second line contains n integers representing the elements of the array.
Print a single integer — the minimum number of distinct integers that can remain after removing exactly k elements.
1 ≤ n ≤ 10^5 0 ≤ k ≤ n 1 ≤ array elements ≤ 10^9
Example 1
Input
5 2 4 4 1 3 3
Output
2
Explanation
Remove two elements of the integer '1' or one from '1' and one from '3' to reduce distinct counts to 2.