Array Painting
Description
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?
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$).
Print one integer — the minimum number of coins you have to spend in order to paint all elements red.
Input
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$).
Output
Print one integer — the minimum number of coins you have to spend in order to paint all elements red.
3
0 2 0
4
0 0 1 1
7
0 1 0 0 1 0 2
1
2
4
Note
In the first example, you can paint all elements red with having to spend only one coin as follows:
- paint the $2$-nd element red by spending one coin;
- decrease the $2$-nd element by $1$ and paint the $1$-st element red;
- 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:
- paint the $4$-th element red by spending one coin;
- decrease the $4$-th element by $1$ and paint the $3$-rd element red;
- paint the $1$-st element red by spending one coin;
- decrease the $3$-rd element by $1$ and paint the $2$-nd element red.