CF1400E.Clear the Multiset

You have a multiset containing several integers. Initially, it contains $a_1$ elements equal to $1$ , $a_2$ elements equal to $2$ , ..., $a_n$ elements equal to $n$ .

You may apply two types of operations:

• choose two integers $l$ and $r$ ( $l \le r$ ), then remove one occurrence of $l$ , one occurrence of $l + 1$ , ..., one occurrence of $r$ from the multiset. This operation can be applied only if each number from $l$ to $r$ occurs at least once in the multiset;
• choose two integers $i$ and $x$ ( $x \ge 1$ ), then remove $x$ occurrences of $i$ from the multiset. This operation can be applied only if the multiset contains at least $x$ occurrences of $i$ .

What is the minimum number of operations required to delete all elements from the multiset?

The first line contains one integer $n$ ( $1 \le n \le 5000$ ).

The second line contains $n$ integers $a_1$ , $a_2$ , ..., $a_n$ ( $0 \le a_i \le 10^9$ ).

Print one integer — the minimum number of operations required to delete all elements from the multiset.