Clear the Multiset
Description
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.
Input
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$).
Output
Print one integer — the minimum number of operations required to delete all elements from the multiset.
Samples
4
1 4 1 1
2
5
1 0 1 0 1
3