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?

你有一个多重集合，其中包含若干个整数。初始时，该多重集合包含 $a_1$ 个值为 $1$ 的元素、$a_2$ 个值为 $2$ 的元素、……、$a_n$ 个值为 $n$ 的元素。

你可以执行以下两类操作：

• 选择两个整数 $l$ 和 $r$（满足 $l \le r$），然后从多重集合中各移除一个 $l$、一个 $l + 1$、……、一个 $r$；该操作仅在多重集合中每个从 $l$ 到 $r$ 的整数至少出现一次时才可执行；
• 选择两个整数 $i$ 和 $x$（满足 $x \ge 1$），然后从多重集合中移除 $x$ 个值为 $i$ 的元素；该操作仅在多重集合中值为 $i$ 的元素至少有 $x$ 个时才可执行。

问：删除多重集合中所有元素所需的最少操作次数是多少？

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

第一行包含一个整数 $n$（$1 \le n \le 5000$）。

第二行包含 $n$ 个整数 $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.

输出一个整数——从多重集中删除所有元素所需的最少操作次数。