Hide

Problem M
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?

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

Please log in to submit a solution to this problem

Log in