Clear the Multiset

给定一个长度为$n$数列$\{a_n\}$，你可以进行如下操作： - 任意选择一个区间$[l,r](l\le r)$，使区间内的每一个数减$1$； - 任意选择一个点$p$和一个正整数$x(x\ge 1$，使$a_p$减去$x$。 求把原数列全部变为$0$的最少的操作次数。 $1\le n\le 5000$，$0\le a_i\le 10^9$。

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.

4
1 4 1 1

2

5
1 0 1 0 1

3