P7399 [COCI 2020/2021 #5] Po

There is an array of length $n$. In the initial state, all elements are $0$. In each operation, you may add a positive integer $x$ to all numbers in a continuous interval $[l,r]$, but it is required that for any two operation intervals, they are either disjoint, or one contains the other. Find the minimum number of operations needed to transform the original array into the given array $a$.

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

Output the minimum number of operations required.

#### Explanation for Sample 2 One optimal plan is: add $2$ to all elements, then add $1$ to the middle three elements. #### Constraints For the testdata worth $30$ points, $1 \le n \le 1000$. For $100\%$ of the testdata, $1 \le n \le 10^5$, $0 \le a_i \le 10^9$. #### Notes **The score of this problem follows the original COCI settings, with a full score of $70$.** **Translated from [COCI2020-2021](https://hsin.hr/coci/) [CONTEST #5](https://hsin.hr/coci/contest5_tasks.pdf) _T2 Po_.** Translated by ChatGPT 5