您有一个包含多个整数的多重集。最初,它包含等于$$$1$$$的$$$a_1$$$元素,等于$$$2$$$的$$$a_2$$$元素,...,等于$$$n$$$的$$$a_n$$$元素。
您可以应用两种类型的操作:
- 选择两个整数 $$$l$$$ 和 $$$r$$$ ($$$l \le r$$$),然后从多重集中删除一次出现的 $$$l$$$、一次出现的 $$$l + 1$$$、...、一次出现的 $$$r$$$。仅当从 $$$l$$$ 到 $$$r$$$ 的每个数字在多重集中至少出现一次时才能应用此操作;
- 选择两个整数 $$$i$$$ 和 $$$x$$$ ($$$x \ge 1$$$),然后从多重集中删除 $$$x$$$ 出现的 $$$i$$$ 。仅当多重集至少包含 $$$x$$$ 次 $$$i$$$ 时才可以应用此操作。
从多重集中删除所有元素所需的最少操作次数是多少?
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5000$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 \le a_i \le 10^9$$$)。
输出
打印一个整数 — 从多重集中删除所有元素所需的最少操作数。
示例
输入 #1
4 1 4 1 1
输出 #1
2
输入 #2
5 1 0 1 0 1
输出 #2
3