Minimum Number of Increments on Subarrays to Form a Target Array

Start from an all-zero array with the same length as target. In each operation, choose a non-empty contiguous range and add 1 to every element in it. Find the minimum number of operations needed to form target.

输入格式

The first line contains n and the second line contains target. The original bounds are 1≤n≤100000, 1≤target[i]≤100000, and the answer is guaranteed to be ≤2147483647; this is a joint constraint, so no array whose answer exceeds 32 bits should be generated.

输出格式

Output a single integer, the answer.

样例 1

输入：

5
1 2 3 2 1

输出：

3

样例 2

输入：

5
3 1 5 4 2

输出：

7

样例 3

输入：

2
2 2

输出：

2

样例说明

The answers are 3, 7 and 2. A valid seven-step sequence for the second example is 00000→11111→21111→31111→31222→31332→31442→31542; this corrects the source's display error, whose last step was not a range +1.