CF1849D Array Painting

给定一个长度为 $n$ 的整数数组，每个整数都是 $0$、$1$ 或 $2$。初始时，数组中的每个元素都是蓝色的。 你的目标是将数组中的每个元素都涂成红色。为此，你可以进行两种操作： - 花费一枚硬币，选择一个蓝色元素并将其涂成红色； - 选择一个已经是红色且不等于 $0$ 的元素，以及与其相邻的一个蓝色元素，将该红色元素的值减 $1$，并将相邻的蓝色元素涂成红色。 你需要花费的最少硬币数是多少，才能将所有元素都涂成红色？

第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$）。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 2$）。

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

在第一个样例中，你只需花费一枚硬币即可将所有元素都涂成红色，操作如下： 1. 花费一枚硬币将第 $2$ 个元素涂成红色； 2. 将第 $2$ 个元素的值减 $1$，并将第 $1$ 个元素涂成红色； 3. 再将第 $2$ 个元素的值减 $1$，并将第 $3$ 个元素涂成红色。 在第二个样例中，你只需花费两枚硬币即可将所有元素都涂成红色，操作如下： 1. 花费一枚硬币将第 $4$ 个元素涂成红色； 2. 将第 $4$ 个元素的值减 $1$，并将第 $3$ 个元素涂成红色； 3. 花费一枚硬币将第 $1$ 个元素涂成红色； 4. 将第 $3$ 个元素的值减 $1$，并将第 $2$ 个元素涂成红色。 由 ChatGPT 4.1 翻译