Description

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$.

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.

3
2 2 2

1

5
2 3 3 3 2

2

6
1 2 3 2 1 3

4

Hint

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 CONTEST #5 T2 Po.

Translated by ChatGPT 5