Under construction

Still being built. Things may change

Ducks and the Clapping Chunbae

Interview

Time limit1sMemory limit1024 MB

Summary
Given N quack times and a window K, find the fewest claps so that every interval [X_i, X_i+K] contains at least one clap.
Level

Medium4 of 10

Topics
Greedy, Sorting, Intervals
Solved
No attempts yet

Problem

Chunbae came to see the ducks. The duck quacks a total of NN times while Chunbae is there. Moved by the quacks, Chunbae claps for the duck.

If the duck quacks at time XiX_i seconds, Chunbae must clap at least once between XiX_i and Xi+KX_i+K seconds, inclusive.

If the duck gets no applause between XiX_i and Xi+KX_i+K seconds after a quack, it is disappointed and goes home. For example, if K=2K=2 and Xi=5X_i=5, Chunbae must clap at least once at 5, 6, or 7 seconds.

Find the minimum number of claps Chunbae must make so that the duck does not go home.

Input

The first line contains the number of quacks NN and the integer KK, separated by a space. (1≤N≤100 0001 \le N \le 100\,000, 0≤K≤1060 \le K \le 10^6)

The second line contains the times X1,X2,…,XNX_1, X_2, \ldots, X_N at which the duck quacks, separated by spaces. The XiX_i are distinct and given in ascending order. (1≤Xi≤1061 \le X_i \le 10^6)

Output

Print the minimum number of claps Chunbae must make so that the duck does not go home.

Examples1

  1. Example 1

    Input
    3 3
    1 3 7
    
    Expected output
    2