Rabbit Carrot

시간 제한1초메모리 제한1024 MB

요약

기둥 높이들이 주어질 때, 높이 0에서 시작해 매 기둥을 최대 M만큼만 올라가며 이동할 수 있도록 높이를 바꿔야 하는 기둥 수의 최솟값을 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 배열, 그리디
정답자: 아직 제출이 없습니다

문제

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$

예제2

예제 1
입력
```
5 400
300
700
200
1000
500
```
예상 출력
```
1
```
예제 2
입력
```
3 300
700
1000
1300
```
예상 출력
```
3
```