← 返回题目列表

Codeforces · 1849/D

D. 阵列绘画

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

给定一个 $$$n$$$ 整数数组,其中每个整数要么是 $$$0$$$、$$$1$$$ 要么 $$$2$$$。最初,数组的每个元素都是蓝色的。

您的目标是将数组的每个元素涂成红色。为此,您可以执行两种类型的操作:

- 支付一枚硬币来选择蓝色元素并将其涂成红色;
- 选择一个不等于 $$$0$$$ 的红色元素和与其相邻的蓝色元素,将所选红色元素减少 $$$1$$$,并将所选蓝色元素涂成红色。

要实现目标,您至少需要花费多少金币?

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2$$$)。

输出

打印一个整数 - 将所有元素涂成红色所需花费的最少硬币数。

示例

输入 #1

3
0 2 0

输出 #1

1

输入 #2

4
0 0 1 1

输出 #2

2

输入 #3

7
0 1 0 0 1 0 2

输出 #3

4

注意

在第一个示例中,您只需花费一枚硬币即可将所有元素涂成红色,如下所示:

1.花费一枚硬币将$$$2$$$-nd元素涂成红色;
2. 将$$$2$$$-nd 元素减少$$$1$$$,并将$$$1$$$-st 元素涂成红色;
3. 将 $$$2$$$-nd 元素减少 $$$1$$$ 并将 $$$3$$$-rd 元素涂成红色。

在第二个示例中,您只需花费两枚硬币即可将所有元素涂成红色,如下所示:

1.花费一枚硬币将第$$$4$$$个元素涂成红色;
2. 将第 $$$4$$$-th 元素减少 $$$1$$$,并将 $$$3$$$-rd 元素涂成红色;
3.花费一枚硬币将$$$1$$$-st元素涂成红色;
4. 将 $$$3$$$-rd 元素减少 $$$1$$$ 并将 $$$2$$$-nd 元素涂成红色。