Regulate Temperatures

Each operation is exactly one of the following: decrease every element of some non-empty prefix by 1; decrease every element of some non-empty suffix by 1; or increase the whole array by 1. Find the minimum number of operations to make all temperatures 0. A single operation cannot decrease by more than one unit, and you cannot decrease an arbitrary interior range by 1.

输入格式

The first line contains n and the second line contains temperature. On this site 1≤n≤200000, −10^9≤temperature[i]≤10^9. The raw fully restores the ranges of the prefix/suffix operations, which the cleaned-up HTML had swallowed.

输出格式

Output a single integer, the answer.

样例 1

输入：

3
2 4 4

输出：

4

样例 2

输入：

4
2 -2 -3 1

输出：

12

样例 3

输入：

2
0 0

输出：

0

样例说明

The answers are 4, 12 and 0. Original example 2 is labeled 10, which is wrong: its first step takes the last temperature from 1 to −2, which already violates the single −1 per operation. This site openly corrects it to 12: three whole-array +1 operations give [5,1,0,4], then the prefix ending at 0 is decreased by 1 four times, the prefix ending at 1 once, and the suffix starting at 3 four times, for 12 operations in total. An independent graph over unit operations confirms this optimum.