Problem J. Jump-herding

Author:М. Спорышев   Time limit:1 sec
Input file:Standard input   Memory limit:512 Mb
Output file:Standard output  


Young farmer Alice has N grasshoppers. Grasshoppers sit along the line, i-th grasshopper at coordinate xi, measured in centimeters. Several grasshoppers may occupy the same point. A grasshopper is alone, if there is no other grasshopper at its position.

Alice wants to herd grasshoppers into the box which is located at position 0.

To do that, Alice can move to any point p on the line and clap loudly. After each clap, any grasshopper that is either

jumps C centimeters to the left.

Once grasshopper reaches the box, it stays there and does not jump anymore.

Your program must determine the minimum number of claps required to get all grasshoppers into the box.

Input format

First line of input contains two integers N and C.

Next line contains N integers xi in ascending order.

Output format

Output must contain a single integer — the minimum number of claps.


1 ≤ N, C ≤ 105

1 ≤ xi − 1 ≤ xi ≤ 109

Sample tests

No. Standard input Standard output
3 1
1 2 3
5 3
1 2 2 3 3

0.037s 0.007s 15