← 返回题目列表

Codeforces · 1400/E

E. 清除多重设置

中文机器翻译题面 查看原题

您有一个包含多个整数的多重集。最初,它包含等于$$$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