Making Numbers Equal

There are $n$ natural numbers $A[1], A[2], A[3], \ldots, A[n]$ arranged in a line, where $1 \le n \le 1{,}000$. One operation Add(i) increases by 1 the entire maximal contiguous block of equal values that contains $A[i]$. In other words, every element equal to $A[i]$ and connected to it through adjacent equal elements increases together. $A[1]$ and $A[n]$ are not adjacent.

For instance, suppose the array is ${1, 1, 1, 1, 3, 3, 1}$. If Add(2) is performed, the first four 1s increase together and the array becomes ${2, 2, 2, 2, 3, 3, 1}$. If Add(4) is then performed, it becomes ${3, 3, 3, 3, 3, 3, 1}$. Performing Add(1) after that makes it ${4, 4, 4, 4, 4, 4, 1}$.

Using Add operations, make all elements have the same value. Find the minimum number of Add operations required.

The first line contains the integer $n$. The next $n$ lines contain $A[1], A[2], \ldots, A[n]$ in order. Every input value is a natural number not greater than $1{,}000{,}000{,}000$.

Print the minimum number of Add operations required to make all elements equal. This value is not greater than $10^{25}$.