Problem F
Don't Fall Down Stairs
King Whomp is walking down Whomp Fortress to fight Mario. In order to get down, he must descend down a staircase consisting of $N$ steps. The height of every subsequent step is less than or equal to the step before (so that he can reach Mario at the end of the staircase).
However, King Whomp is injured these days, so he cannot walk down steps that have a height difference of more than $1$. Thus, his Whomp underlings keep adjusting the staircase by removing one brick from the current step, which decreases the height of the current step by $1$, or adding one brick to the next step to raise its height by $1$ in order to keep their Majesty safe.
Every brick that the Whomps add or remove costs one unit of effort for them. Can you help them calculate the minimum amount of effort needed to help King Whomp walk from Whomp Fortress to Mario, who is on the ground at height 0?
Input
The first line of the input is an integer $N$ ($1
\leq N \leq 1\, 000 \, 000$), representing the number of
steps.
The second line of input contains $N$ space separated integers
$a_1, a_2, \ldots , a_ n$
($1 \leq a_ i \leq 1\, 000 \,
000$) representing the height of each step where
$a_1 \geq a_2 \geq \ldots a_
n$. Note that King Whomp needs to travel from the
$n$-th step to the floor,
which is at height 0.
Output
Output one line containing a single integer $E$, the minimum effort of the Whomp underlings to guarantee King Whomp can safely walk down Whomp Fortress.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 9 7 5 4 4 |
5 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 5 4 3 2 |
1 |
