CF1849D.Array Painting

You are given an array of $n$ integers, where each integer is either $0$, $1$, or $2$. Initially, each element of the array is blue.

Your goal is to paint each element of the array red. In order to do so, you can perform operations of two types:

• pay one coin to choose a blue element and paint it red;
• choose a red element which is not equal to $0$ and a blue element adjacent to it, decrease the chosen red element by $1$, and paint the chosen blue element red.

What is the minimum number of coins you have to spend to achieve your goal?

给你一个包含 $n$ 个整数的数组，其中每个整数均为 $0$、$1$ 或 $2$。初始时，数组中每个元素均为蓝色。

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

• 支付一枚硬币，选择一个蓝色元素并将其涂成红色；
• 选择一个非零的红色元素，以及一个与其相邻的蓝色元素；将该红色元素的值减 $1$，并将该蓝色元素涂成红色。

为达成目标，你最少需要支付多少枚硬币？

The first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 2$).

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

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

Print one integer — the minimum number of coins you have to spend in order to paint all elements red.

输出一个整数——即为将所有元素涂成红色所需花费的最少硬币数。

In the first example, you can paint all elements red with having to spend only one coin as follows:

1. paint the $2$-nd element red by spending one coin;
2. decrease the $2$-nd element by $1$ and paint the $1$-st element red;
3. decrease the $2$-nd element by $1$ and paint the $3$-rd element red.

In the second example, you can paint all elements red spending only two coins as follows:

1. paint the $4$-th element red by spending one coin;
2. decrease the $4$-th element by $1$ and paint the $3$-rd element red;
3. paint the $1$-st element red by spending one coin;
4. decrease the $3$-rd element by $1$ and paint the $2$-nd element red.

在第一个例子中，你可以仅花费一枚硬币就将所有元素涂成红色，具体步骤如下：

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

在第二个例子中，你可以仅花费两枚硬币就将所有元素涂成红色，具体步骤如下：

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