No submission language available for this problem.

Description

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

1

4
0 0 1 1

2

7
0 1 0 0 1 0 2

4

Note

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.