#111. Copy

YHZ led ACM teams for many years. As you know, he hates others to copy his homework. Yesterday he met a difficult problem.

He got an array with elements. All are non-negative. He wants to reduce each element to zero. The only operation is choosing an interval, and reduce each element in it by .

He wants to minimize the number of operations, could you help him? Please be reminded that at any time, the elements cannot be negative.

There is only one test case.

The first line contains a integer . The second line contains integers, indicating the elements in the array.

Output only one line. The minimum number of operations.

Sample Input

5
2 3 4 1 2

Sample Output

5

,

In the sample input, one possible way is [1, 5][1, 3][2, 3][3, 3][5, 5]. It can be proved that there are no ways which cost less than 5 operations.