안전

생쥐 Squeaky는 최근 시각 예술에 눈을 떴고, 마을에서 가장 권위 있는 시각 예술 축제에 전시할 자신만의 작품을 만들려고 한다.

그의 작품은 비슷한 크기의 빛나는 정육면체를 여러 개 쌓아 일렬로 배열한 것이다. 더 정확히는, 왼쪽에서 오른쪽으로 1번부터 N번까지 번호가 붙은 N개의 더미가 있고, i번 더미에는 S[i]개의 정육면체가 있다. 다음은 Squeaky의 작품이 될 수 있는 한 가지 예이다.

그림 5: N = 20인 작품 배치의 한 예

정육면체가 매우 무거워서, 정육면체를 쌓아 작품을 완성하는 일은 매우 힘든 작업이었고, Squeaky는 축제가 시작되기 며칠 전에야 조립을 끝낼 수 있었다.

이제 드디어 쉴 수 있으리라 생각한 순간, 안전 위원회가 그의 작품을 심사하러 찾아왔다. 이 축제의 안전 위원회는 작년 축제에서 끔찍한 사고가 일어난 이후로 매우 까다롭고 타협하지 않는다.

Squeaky는 위원회가 서로 모여 조용히 이야기하는 모습을 보고 마음이 철렁 내려앉았다. 그들이 자신의 작품에서 문제를 찾았다는 것을 알았기 때문이다. 결국 위원회의 몇몇 위원이 그에게 다가와 우려를 설명했다. 관람객이 작품에 부딪히면 일부 더미가 넘어질 수도 있다는 것이다. 구체적으로, 인접한 더미의 높이 차가 H개 이하일 때만 작품이 안전하다. 즉, 모든 1 ≤ i ≤ N − 1에 대해 |S[i] − S[i + 1]| ≤ H이다.

그러고 나서 그들은 그에게 두 가지 선택지를 주었다. 작품을 안전하게 고치거나, 작품을 완전히 철거하거나.

물론 이 작품에 그렇게 많은 공을 들인 Squeaky는 작품을 철거하는 것을 선택지로 고려하지 않았고, 정육면체를 더하고 빼서 작품을 고치기로 했다. 정육면체를 옮기는 일은 힘들기 때문에, 그는 해야 할 작업량을 최소화하려고 한다.

형식적으로, 그는 작품을 안전하게 만드는 데 필요한 단계 수를 최소화하려고 하며, 각 단계는 다음 중 하나이다.

• k번 더미의 꼭대기에 정육면체 하나를 더한다.
• k번 더미의 꼭대기에서 정육면체 하나를 뺀다.

Squeaky가 작품을 안전하게 만드는 데 필요한 최소 단계 수를 구하도록 도와주자.

프로그램은 표준 입력에서 입력을 읽는다.

입력의 첫 번째 줄에는 두 개의 양의 정수 N과 H가 주어진다.

입력의 두 번째 줄에는 N개의 음이 아닌 정수가 주어진다. 이 줄의 i번째 정수는 S[i]이다.

프로그램은 작품을 안전하게 만드는 데 필요한 최소 연산 수를 나타내는 정수 하나를 출력한다.

• 1 ≤ N ≤ 200 000
• 0 ≤ H ≤ 1 000 000 000
• 모든 1 ≤ i ≤ N에 대해 0 ≤ S[i] ≤ 1 000 000 000