벽

회사 <>는 새로운 자동화 산업용 로봇 SCV-2 모델을 위한 인공지능을 개발하고 있다. 현재 단계에서는 표준 건축 블록으로 쌓은 벽을 짓고 수리하는 로봇을 만든다.

우선 같은 크기의 블록으로 이루어진 벽을 다루는 단순화된 로봇 모델을 만들기로 했다. 벽은 블록으로 쌓은 기둥의 나열이며, 이런 벽의 예가 그림 1에 있다.

그림 1

첫 번째 로봇 모델은 정확히 하나의 기본 동작만 할 수 있다. 어떤 기둥의 맨 위 블록을 집어서 이웃한 기둥 위에 놓는 것이다. 이때 벽의 끝 옆에 블록을 놓아 새 기둥을 만드는 것은 허용되지 않는다.

인공지능을 위한 시험 과제로 벽 고르기 문제가 주어졌다. 벽의 임의의 두 기둥 높이 차이가 1 이하이면 그 벽을 고르다고 한다. 고르는 과정에서 로봇은 기본 동작을 사용해 주어진 벽을 임의의 고른 벽으로 바꿔야 한다. 이때 수행한 기본 동작의 수는 최소여야 하고, 벽의 기둥 수는 변하지 않아야 한다.

예를 들어 그림 1의 벽은 네 번의 기본 동작으로 그림 2의 고른 벽으로 바꿀 수 있으며, 이 벽에서 이 동작 수가 최소이다.

그림 2

인공지능 개발자가 만든 알고리즘을 검증할 수 있도록, 주어진 벽을 고르게 만드는 데 로봇이 해야 하는 최소 동작 수를 구하자.

첫째 줄에 벽을 이루는 세로줄의 수 $n$이 정수로 주어진다 ($1 \le n \le 1000$). 둘째 줄에는 $a\_1, a\_2, \ldots, a\_n$이 주어지며, $a\_i$는 $i$번째 기둥의 블록 수이다 ($1 \le a\_i \le 10^6$).

벽을 고르게 만드는 데 필요한 최소 블록 이동 수를 정수 하나로 출력한다.