# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Sroud loves to play PUBG and does programming contest. He always thinks about converting gameplay to programming, and most of the times he gets weird idea. The problem mentioned below is the output of one of those weird ideas.

In PUBG there are several play zones, and players should cross these play zones from starting to final play zone by car (if he has one) or by running. But in this special weird idea, one always has a car with him. But there are some weird instructions also to drive a car.

- The road is straight.
- There is only one button for a car, by pressing the button (as many time as one wants) the car moves exactly
**X**meter forward. - The only dependency is that, the car from any play zone cannot move to another play zone(Remember, one will get a new car at the starting of each play zone). i.e you can not press the button if there is a possibility to cross the play zone with car. So the remaining path has to be covered by running.

Now, Sroud is excited to find the size of path one has to cover by running to cross each play zone from starting to final play zone.

Input starts with an Integer **N** and **X** denoting the number of play zones and the size of path a car moves forward by pressing the button mentioned above.

Second line contains **N** space separated integers *a*_{1}, *a*_{2},…, *a*_{N}, where *a*_{i} denotes the size of the *i*^{th} play zone.

**Constraints:**

1 ≤ **N** ≤ 2×10^{5}

(1 ≤ *a*_{i}, **X** ≤ 10^{9})

Print an integer **k** — denoting the size of path one has to cover by running.

Input | Output |
---|---|

3 8 4 10 1 | 7 |

93% Solution Ratio

Riaz_BSMRSTUEarliest,

ishtupeedFastest, 0.0s

Riaz_BSMRSTULightest, 131 kB

mdvirusShortest, 99B

Login to submit