H :: Greedy Garshausp

Time Limit: 3 Seconds    Memory Limit: 65536 KB

Garshausp, a second year undergraduate student in computer engineering, is participating in a programming contest. One of the problems named “Intervals” is described as follows.

The input to the “Intervals” problem is a set of points on the X axis and a length . The problem is to cover all the points using intervals of length . For example, having the points {1, 4, 10} and , we can cover the points using two intervals of length 5, say [1,6] and [7,12]. Note that there are many more solutions, but all of them consist of at least two intervals. The problem is to compute the minimum number of intervals required to cover all the points.

Trying to solve the problem, Garshausp comes up with a greedy algorithm: at each step, choose the maximal set of points that can be covered by one interval, and cover them. Repeat this process until all points are covered. If in one step, there are more than one maximal set of points that could be covered by one interval, choose the leftmost one. Unfortunately, Garshausp’s algorithm is not optimal and he cannot get “Yes” for “Intervals”.

No! Your problem is NOT to solve the “Intervals” problem! Rather, you must write a program that given a set of points and a length , determines the number of intervals that Garshausp’s algorithm suggests for covering the points.

Input

There are multiple test cases in the input. Each test case starts with a line containing two space-separated integers n ( 1 <= n <= 105 ) and C ( 0 <= C <= 109 ), where n is the number of points to cover and C is the interval length. The next line contains n space-separated integers specifying the location of the points on the X axis. All these numbers are nonnegative and no more than 109.

The input terminates with a line of the form "0 0" (without quotation marks) which should not be processed as a test case.

Output

For each test case, write a single line containing the number of intervals of length C that Garshausp’s algorithm uses to cover all the points.

Sample Input

4 2
1 2 3 4
4 2
1 3 5 7
4 2
1 4 7 10
0 0

Sample Output

2
2
4
Submit

Source: 9th Iran Nationwide Internet Contest