给定一个 $$$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 元素涂成红色。