25959번 - 계단 만들기 (Large)

문제

때는 2013년, 잼민이 지수는 마인크래프트 게임을 열심히 하고 있다.

지수가 하는 마인크래프트에서는 점프는 한 칸밖에 되지 않으며, 신기하게도 두 칸 이상부터 즉사 낙하 데미지가 들어간다! 따라서 한 곳에서 다른 한 곳으로 이동하기 위해서는 인접한 열의 높이 차가 1ドル$ 이하여야만 한다. 또한, 모든 블록은 공중에 떠 있을 수 없다.

위 그림에서처럼 지수는 왼쪽 끝에서 오른쪽 끝으로 이동하고자 한다. 그런데 지금 상태에서는 인접한 열의 높이 차가 2ドル$ 이상인 곳이 있어 지수의 캐릭터가 즉사하게 된다. 따라서 몇 개의 블록을 옮겨 블록의 높이 차가 최대 1ドル$이 되게 하고자 한다. 그러나 지수는 매우 게으른 성격이기 때문에 최소한의 블록만 옮기고 싶다.

위 예시에서는 두 개의 블록을 옮기면 모든 인접한 블록의 높이 차가 최대 1ドル$이 된다!

지수가 왼쪽 끝에서 오른쪽 끝으로 안전하게 도달하기 위해 블록을 옮길 때, 옮겨야 하는 블록의 최소 개수를 구하시오.

입력

첫 번째 줄에 정수 $N$이 주어진다. $N$은 마인크래프트 맵의 너비이다. (1ドル \le N \le 100$)

두 번째 줄에는 $N$개의 수가 주어진다. $i$ 번째 수 $h_i$는 $(i - 1)$ 좌표에 놓인 블록의 높이이다. (1ドル \le h_i \le 1\ 000\ 000$)

출력

첫 번째 줄에 옮겨야 하는 블록의 최소 수를 한 개의 정수로 출력하시오.

제한

힌트