Hide

Problem H
Voff

Languages en is
/problems/voff/file/statement/en/img-0001.jpg
Image from wikimedia.org
Atli is sunbathing on this wonderful day—nothing could be better.

Then suddenly Atli hears a bark, then another and then over and over. Atli finds the barking quite annoying but he always tries to make the best of a situation so he tries to turn this into a puzzle to solve.

First Atli writes down the current second every time he hears a bark, denoted by a single integer ai. The time of the first bark is then a1 and the time of the last is an. In Atli’s reality dogs need at least k seconds between barks to breathe.

Thus Atli decides that the puzzle is what the minimum number of dogs that could be barking is. Atli finds this to be a reasonable puzzle. Can you solve it?

Input

The input is two lines. The first line contains two integers 1n,k105. The second line contains n integers 1ai109.

Output

Print a single integer, the minimum number of dogs that could be barking.

Scoring

Group

Points

Constraints

1

15

1n,ai100,k=1

2

35

1n,k,ai100

3

50

No further constraints

Sample Input 1 Sample Output 1
3 1
1 2 3
1
Sample Input 2 Sample Output 2
3 2
1 2 3
2
Sample Input 3 Sample Output 3
3 3
1 2 3
3
Sample Input 4 Sample Output 4
3 4
1 2 3
3
Hide

Please log in to submit a solution to this problem

Log in