Problem M
Meticulous smoothing
Your plank is $n$ cm long, and the arts and crafts teacher has measured the width of your plank on $k$ different locations to prove his point. He demands that the thickness should differ by no more than $1$ micrometer between any two consecutive measured location. If the sandpaper will shave off $1$ micrometer of wood each time you use it at a particular location, how many times do you need to use the sandpaper?
Input
The first line of input contains a single integer $1 \leq n \leq 10^6$, the length of your plank. On the second line of input follows $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 that the sandpaper only touch one location at the same time).
| Sample Input 1 | Sample Output 1 |
|---|---|
5 1 6 7 2 5 |
10 |
