24249번 - Meticulous smoothing 다국어

The arts and crafts teacher is looking at the beautiful plank you crafted in the woodshop, and gaze at you with a stern look. "This is not smooth enough! Use more sandpaper!"

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?

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