Make all numbers equal 2

A sequence of $n$ natural numbers $A[1], A[2], \dots, A[n]$ is given. The operation Add(i) raises $A[i]$ by 1. It does not touch $A[i]$ alone: the whole run of neighboring positions that currently hold the same value as $A[i]$ goes up by 1 at once. $A[1]$ and $A[n]$ are not adjacent.

Look at the sequence {1, 1, 1, 1, 3, 3, 1}. Add(2) raises $A[2]$ together with the equal values next to it and gives {2, 2, 2, 2, 3, 3, 1}. Add(4) then gives {3, 3, 3, 3, 3, 3, 1}, and Add(1) after that gives {4, 4, 4, 4, 4, 4, 1}.

You want to use the Add operation several times until $A[1] = A[2] = \dots = A[n]$. Find the smallest number of Add operations that is enough.

The first line contains the integer $n$. Each of the next $n$ lines contains one value, $A[1]$ through $A[n]$ in order.

$1 \le n \le 10^6$, and every $A[i]$ is a natural number no greater than $10^9$.

Print the smallest number of Add operations on the first line.