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 $a_i$. The time of the first bark is then $a_1$ and the time of the last is $a_n$. 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 $1 \le n,k \le 10^5$. The second line contains $n$ integers $1 \le a_i \le 10^9$.

Output

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

Scoring

Group

Points

Constraints

1

15

$1 \le n,a_i \le 100, k = 1 $

2

35

$1 \le n,k,a_i \le 100 $

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