## Problem J. Jump-herding ≡

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

### Statement

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

• located exactly at point p, or
• is alone,
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.

### Constraints

1 ≤ N, C ≤ 105

1 ≤ xi − 1 ≤ xi ≤ 109

### Sample tests

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

0.037s 0.007s 15