Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

greedy

two pointers

*1700

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Array Painting

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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?

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.

Examples

Input

3 0 2 0

Output

1

Input

4 0 0 1 1

Output

2

Input

7 0 1 0 0 1 0 2

Output

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/15/2024 19:55:47 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|