Meticulous smoothing

Interview

Time limit1sMemory limit1024 MB

Summary

Given a plank's thickness at n positions, shave off 1 micrometer at a time so that neighboring thicknesses differ by at most 1; find the minimum number of shaves.

Level: Medium5 of 10
Topics: Dynamic programming, Greedy, Array, Prefix sum
Solved: No attempts yet

Problem

The arts and crafts teacher looks at the beautiful plank you made in woodshop and fixes you with a stern stare. "This is not smooth enough! Use more sandpaper!"

Your plank is $n$ cm long, and to prove his point the teacher measured its thickness at $k$ different locations. He demands that the thickness differ by no more than $1$ micrometer between any two consecutive measured locations. Each time you use the sandpaper at a particular location, it shaves off $1$ micrometer of wood. How many times do you need to use the sandpaper?

Input

The first line contains a single integer $1 \leq n \leq 10^6$ , the length of your plank. The second line contains $n$ space-separated integers $k_1, k_2, \ldots, k_n$ , the thickness of your plank ( $1 \leq k_i \leq 10^6$ for every $i$ ).

Output

Output a single integer, the minimum number of times you need to use the sandpaper (assuming the sandpaper touches only one location at a time).

Examples1

Example 1
Input
```
5
1 6 7 2 5
```
Expected output
```
10
```