같은 수로 만들기 2

시간 제한2초메모리 제한512 MB

요약

같은 값을 가진 이웃 구간 전체를 한 번에 1 올리는 Add 연산으로 모든 값을 같게 만드는 최소 횟수를 구한다.

난이도: 보통10점 중 5점
유형: 그리디, 구현
정답자: 아직 제출이 없습니다

문제

자연수 $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 연산의 최소 횟수를 출력한다.

예제2

예제 1
입력
```
3
1
5
10
```
예상 출력
```
9
```
예제 2
입력
```
7
1
1
1
1
3
3
1
```
예상 출력
```
4
```