数组染色

时间限制：2s
空间限制：256MB

题目描述

给定一个长度为 $n$ 的整数数组，每个整数都是 $0$、$1$ 或 $2$。初始时，数组中的每个元素都是蓝色的。

你的目标是将数组中的每个元素都涂成红色。为此，你可以进行两种操作：

• 花费一枚硬币，选择一个蓝色元素并将其涂成红色；
• 选择一个已经是红色且不等于 $0$ 的元素，以及与其相邻的一个蓝色元素，将该红色元素的值减 $1$，并将相邻的蓝色元素涂成红色。

你需要花费的最少硬币数是多少，才能将所有元素都涂成红色？

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$。

输出格式

输出一个整数，表示将所有元素都涂成红色所需花费的最少硬币数。

样例输入 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$ 个元素涂成红色；
2. 将第 $2$ 个元素的值减 $1$，并将第 $1$ 个元素涂成红色；
3. 再将第 $2$ 个元素的值减 $1$，并将第 $3$ 个元素涂成红色。

在第二个样例中，你只需花费两枚硬币即可将所有元素都涂成红色，操作如下：

1. 花费一枚硬币将第 $4$ 个元素涂成红色；
2. 将第 $4$ 个元素的值减 $1$，并将第 $3$ 个元素涂成红色；
3. 花费一枚硬币将第 $1$ 个元素涂成红色；
4. 将第 $3$ 个元素的值减 $1$，并将第 $2$ 个元素涂成红色。

数据范围

• 对于所有数据，满足 $1\le n\le2\times10^5$。
• 对于所有数据，满足 $0\le a_i\le2$。