Optum Q2 :
Difficulty Level : Easy
Submissions : 81
Asked In :
Marks :10
: 1 | : 0
There are 2 boys in a class who have been given a target, $$$k$$$ by their class teacher. The students have an array of $$$n$$$ elements $$$a_i$$$. Their task to remove the minimum number of elements from this array such that the absolute difference between any two elements in the resulting array is lesser than or equal to k. Find the minimum number of elements that the boys need to remove from the array.
Constraints
- $$$1 \leq n \leq 100000$$$
- $$$1 \leq arr[i] \leq 100000$$$
Input
The first line of the input contains two integers $$$n$$$ and $$$k$$$ representing the length of the array and the maximum difference desired. The next line contains a sequence of n integers $$$a_i$$$
Output
Output a single integer which is the answer to the problem
Example
Input
3 3 5 10 2
Output
1
