488. Partition Array to Minimize Difference

0

Medium

Given an array of integers nums and an integer k, you need to partition nums into one or more subsequences. Each element in nums must appear in exactly one subsequence. Find the minimum number of subsequences needed such that the difference between the maximum and minimum values in each subsequence is at most k. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Input Format

The first line of input contains two space-separated integers N (the size of the array) and K. The second line consists of N space-separated integers representing the elements of the array.

Output Format

Output an integer representing the minimum number of subsequences required.

Example

Input

5 2
3 6 1 2 5

Output

2

Constraints

1 <= N <= 10^4

Loading...

View Submissions

Console