모든 수가 양의 정수인 길이 $n$의 수열 $a_1, a_2, ... , a_n$이 주어진다. 아래 연산을 최소한으로 수행해 수열의 모든 수를 같게 만들 수 있을까?

• $1 ≤ l ≤ r ≤ n$ 인 $l, r$을 고른 후 $[l, r]$에 $1$을 더한다.

예를 들어 수열이 $5, 3, 2, 2, 5$ 라고 하자. $[2, 2]$에 $2$번의 연산을 적용한 뒤 $[3, 4]$에 $3$번의 연산을 적용하면 $5$번의 연산으로 모든 수를 같게 만들 수 있다.

한편, $[2, 4]$에 $2$번의 연산만 적용한 뒤 $[3, 4]$에 $1$번의 연산을 적용하면 $3$번의 연산으로 모든 수를 같게 만들 수 있고, 이보다 적게 연산을 수행해 모든 수를 같게 만드는 방법은 없다.

첫째 줄에 수열의 길이를 의미하는 정수 $n$이 주어진다. $(1 ≤ n ≤ 100,000)$

둘째 줄에 $a_1, a_2, ... , a_n$이 공백으로 구분되어 주어진다. $(1 ≤ a_i ≤ 10^9)$