JUNGOL

한국 현대예술의 거장인 석표는 마을 축제에 작품을 설치하려 한다. 석표의 작품은 여러 개의 정육면체 모양 큐브를 쌓아 놓은 것으로 표현되며, 앞에서부터 i번째 칸에는 S_i개의 정육면체가 쌓여 있다.

하지만 주최 측에서 안전상의 문제로 작품에 다음과 같은 조건이 적용되어야 한다고 주장했다. 인접한 두 칸에 쌓여 있는 정육면체의 개수의 차가 H이하여야 한다.

하지만 이 사실을 축제 전날 전달받은 석표는 전체적인 설계를 다시 하는것이 아닌, 몇 개의 정육면체를 추가하거나 제거하는 작업을 반복해서 안전 조건을 만족하려 한다. 석표를 도와 수정 연산의 최소 횟수를 구해라.

1 ≤ N ≤ 200 000

0 ≤ H ≤ 1 000 000 000

0 ≤ S[i] ≤ 1 000 000 000

입력

N H

S_1 S_2 ... S_N

출력

첫 번쨰 줄에 수정 연산의 최소 횟수를 출력하여라.

안전제일 1s 512MB