Maximum New Flowers

You are given an arrangement of n flowerbeds represented by an array where each element is either 0 (empty) or 1 (a flower is already planted). Your task is to determine the maximum number of new flowers that can be planted without violating the rule that no two adjacent flowerbeds can have a flower.

Note: When planting a flower, both its immediate left and right neighbors (if they exist) must be empty.

Mathematically, if we denote the flowerbeds as an array \( A = [a_0, a_1, \dots, a_{n-1}] \), then you can plant a flower at index \( i \) if and only if \[ a_i = 0 \quad \text{and} \quad (i = 0 \;\text{or}\; a_{i-1} = 0) \quad \text{and} \quad (i = n-1 \;\text{or}\; a_{i+1} = 0). \]

Your program should read the input from stdin and write the output to stdout.

inputFormat

The first line contains an integer n representing the number of flowerbeds.

The second line contains n integers separated by spaces, where each integer is either 0 or 1.

outputFormat

Output a single integer representing the maximum number of new flowers that can be planted.

5
1 0 0 0 1

1