같은 수로 만들기

자연수 $n$개 $A[1], A[2], A[3], \ldots, A[n]$이 일렬로 놓여 있다. 단, $1 \le n \le 1{,}000$이다. 연산 Add(i)를 한 번 수행하면 $A[i]$가 속한 같은 값의 연속 구간 전체가 1씩 증가한다. 즉, $A[i]$와 값이 같고 좌우로 인접해 이어진 원소들이 모두 함께 증가한다. $A[1]$과 $A[n]$은 서로 인접하지 않는다.

예를 들어 배열이 ${1, 1, 1, 1, 3, 3, 1}$일 때 Add(2)를 수행하면 앞의 네 개의 1이 함께 증가하여 ${2, 2, 2, 2, 3, 3, 1}$이 된다. 이어서 Add(4)를 수행하면 ${3, 3, 3, 3, 3, 3, 1}$이 되고, 다시 Add(1)을 수행하면 ${4, 4, 4, 4, 4, 4, 1}$이 된다.

Add 연산을 사용해 모든 원소가 같은 값이 되도록 만들고자 한다. 필요한 Add 연산의 최소 횟수를 구하라.

첫째 줄에 정수 $n$이 주어진다. 다음 $n$개의 줄에는 $A[1], A[2], \ldots, A[n]$이 차례로 주어진다. 모든 입력값은 자연수이며 $1{,}000{,}000{,}000$을 넘지 않는다.

모든 원소를 같은 값으로 만들기 위해 필요한 Add 연산의 최소 횟수를 출력한다. 이 값은 $10^{25}$를 넘지 않는다.