Problem E
Scaffolding

by Greg Hume on Wikipedia CC BY-SA

As a construction worker, you want to build a bamboo scaffold for an upcoming festival. There are specific requirements for the final scaffold, which will be part of a vertical, $2$-dimensional grid. $N+1$ vertical long bamboos are already established, so there are $N$ columns in between. Initially all columns are empty. Our task is to place exactly $H_ i$ horizontal short bamboos in the $i$th column, literally from the ground up.

Figure 1: The left diagram illustrates the initial scaffold that has $N$ empty columns. The right diagram shows the final scaffold for Sample Input 2.

You can carry at most $M$ short bamboos at a time. You will install the short bamboos in a number of rounds. In each round, you take at most $M$ short bamboos with you, and start anywhere on ground level.

You can only stand on a short bamboo that was built previously (or on ground level). Then you have two options:

• Climb left, right or up if a short bamboo is already in place there

• Place a short bamboo to the left, right or up if there is no short bamboo already placed

Note that you cannot go down while carrying short bamboos. You cannot place a short bamboo below you either.

Once you finish placing all the short bamboos in the current round, you go down to the ground level. You then take at most $M$ short bamboos with you and start another round from the ground level. This goes on until you have built the desired scaffold, with exactly $H_ i$ short bamboos in column $i$ for all $i$.

What is the minimum number of rounds you need?

Input

The first line contains two integers, $N$ and $M$ ($1 \leq N \leq 100\, 000$, $1 \leq M \leq 10^9$). The second line contains $N$ integers $H_1, \dots , H_ N$ ($0 \leq H_ i \leq 100\, 000$).

Output

Output an integer representing the minimum number of rounds.

3 4
2 1 5

2

5 10
2 1 2 1 2

3