CF1400E Clear 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$ 次时，才能进行此操作。 请问，最少需要多少次操作才能将多重集合中的所有元素全部删除？

第一行包含一个整数 $n$（$1 \le n \le 5000$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^9$）。

输出一个整数，表示最少需要多少次操作才能将多重集合中的所有元素全部删除。

由 ChatGPT 4.1 翻译