Make all numbers equal 2

Time limit2sMemory limit512 MB

Summary

Given a sequence where one Add raises a whole run of equal neighboring values by 1, find the minimum number of Adds to make all values equal.

Level: Medium5 of 10
Topics: Greedy, Implementation
Solved: No attempts yet

Problem

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.

Input

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$ .

Output

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

Examples2

Example 1
Input
```
3
1
5
10
```
Expected output
```
9
```
Example 2
Input
```
7
1
1
1
1
3
3
1
```
Expected output
```
4
```