Rabbit Carrot

Rabbit called Carrot is willing to cross the bridge. The bridge consists of $N$ poles of different height. Carrot can jump at most $M$ centimeters up and any distance down.

The rabbit starts crossing the bridge from the left and is standing at height zero immediately before the first pole. The goal of the Carrot is to reach the other side of the bridge by jumping on each pole in order.

However, it might happen, that the rabbit will not be able to jump on some poles as it will be too high.

Help the rabbit Carrot to cross the bridge by modifying the heights of some poles. Calculate the smallest possible amount of poles the height of which has to be either increased or decreased so that the Carrot could cross the bridge. Height of each of the poles can be increased by any amount and decreased to a non-negative value.

The first line contains two integers: the number of bridge poles $N$ and the Carrot leap-up size $M$. The following $N$ lines contain the heights of the poles $a\_i$ given as integers one number per line.

Output one integer – the least number of poles that have to be either lifted or lowered so that the rabbit Carrot could cross the bridge.

• $1 ≤ N ≤ 200\\,000$
• $0 ≤ M ≤ 5\\,000$
• $0 ≤ a\_i ≤ 10^9$