같은 수로 만들기 2

자연수 $n$개로 이루어진 수열 $A[1], A[2], \dots, A[n]$이 있다. 이 수열에 Add(i) 연산을 하면 $A[i]$가 1 증가한다. 이때 $A[i]$ 하나만 증가하는 것이 아니라, $A[i]$와 값이 같으면서 좌우로 이어져 있는 구간 전체가 한 번에 1씩 증가한다. $A[1]$과 $A[n]$은 인접하지 않는다.

수열이 {1, 1, 1, 1, 3, 3, 1}인 경우를 보자. Add(2)를 하면 $A[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 연산을 여러 번 사용해 $A[1] = A[2] = \dots = A[n]$을 만들려고 한다. 필요한 Add 연산의 최소 횟수를 구하시오.

첫째 줄에 정수 $n$이 주어진다. 다음 $n$개의 줄에 $A[1]$부터 $A[n]$까지 한 줄에 하나씩 순서대로 주어진다.

$1 \le n \le 10^6$이고, 모든 $A[i]$는 $10^9$ 이하의 자연수이다.

첫째 줄에 필요한 Add 연산의 최소 횟수를 출력한다.