https://codeforces.com/contest/1077/problem/B

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

There is a house with nn flats situated on the main street of Berlatov. Vova is watching this house every night. The house can be represented as an array of nn integer numbers a1,a2,…,an, where ai=1 if in the i-th flat the light is on and ai=0 otherwise.

Vova thinks that people in the i-th flats are disturbed and cannot sleep if and only if 1<i<n and ai−1=ai+1=1and ai=0.

Vova is concerned by the following question: what is the minimum number k such that if people from exactly k pairwise distinct flats will turn off the lights then nobody will be disturbed? Your task is to find this number k.

Input

The first line of the input contains one integer n (3≤n≤100) — the number of flats in the house.

The second line of the input contains n integers a1,a2,…,an (ai∈{0,1}), where ai is the state of light in the i-th flat.

Output

Print only one integer — the minimum number k such that if people from exactly k pairwise distinct flats will turn off the light then nobody will be disturbed.

Examples

input

10
1 1 0 1 1 0 1 0 1 0

output

2

input

5
1 1 0 0 0

output

0

input

4
1 1 1 1

output

0

Note

In the first example people from flats 2 and 7 or 4 and 7 can turn off the light and nobody will be disturbed. It can be shown that there is no better answer in this example.

There are no disturbed people in second and third examples.

C++版本一

#include <iostream>
#include <stdio.h>
using namespace std;
typedef long long ll;
int t,n;
int a[100+10];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    int ans=0;
    for(int i=2;i<n;i++){
        if(a[i-1]==1&&a[i+1]==1&&a[i]==0){
            ans++;
            a[i+1]=0;
        }
    }
    cout << ans << endl;
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

The first observation is that we are interested only in patterns of kind "101". All other patterns don't make sense at all.

So, let's build a greedy approach. Let's iterate over the given array from the left to the right and maintain that the prefix of the given answer is already correct. If now we are at some position ii, ai−1=ai+1=1 and ai=0 (and the prefix from 1 to i−2 is already correct) then which one 1 we have to replace? When we replace the left one then we cannot do better in the future, but when we replace the right one then we can fix some on the suffix of the array.

The easiest example is "1101011". If now we are at the position 3 then we will do better if we will set a4:=0.

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	
	int ans = 0;
	for (int i = 1; i < n - 1; ++i) {
		if (a[i] == 0 && a[i - 1] == 1 && a[i + 1] == 1) {
			++ans;
			a[i + 1] = 0;
		}
	}
	cout << ans << endl;
	
	return 0;
}