Problem Description

There is an array of length $n$. Initially, all elements are $0$.

In each operation, you can add a positive integer $x$ to all elements within a continuous interval $[l, r]$, with the condition that any two operation intervals are either disjoint or one contains the other.

Determine the minimum number of operations required to transform the original array into the given array $a$.

Input Format

The first line contains an integer $n$.

The second line contains $n$ non-negative integers $a_i$.

Output Format

Output the minimum number of operations required.

Sample Input and Output

Sample Input #1

3
2 2 2

Sample Output #1

1

Sample Input #2

5
2 3 3 3 2

Sample Output #2

2

Sample Input #3

6
1 2 3 2 1 3

Sample Output #3

4

Notes/Hints

Sample 2 Explanation

An optimal solution is to add $2$ to all elements and then add $1$ to the middle three elements.

Data Size and Constraints

For $30$ points, $1 \le n \le 1000$.

For $100\%$ of the data, $1 \le n \le 10^5$, $0 \le a_i \le 10^9$.

Notes

This problem's score is set according to the original COCI contest, with a full score of $70$.

The problem is translated from COCI2020-2021 CONTEST #5 T2 Po.

见题面 Input 部分

见题面 Output 部分