There is a house withnflats situated on the main street of Berlatov. Vova is watching this house every night. The house can be represented as an array of n integer numbers a1,a2,…,aN, where ai = 1if 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=1 and 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.

题目大意

有一个街区成序列状，其上有n 户人家。夜深了，每个人家有一个属性a 表示改该人家是否开着灯（1 为开，0 为关）。

定义一户人家被打扰，当且仅当该户人家关灯，且该户人家旁边的两家均开着灯。

求至少要关掉多少家的灯，才能让所有的人家均不会被打扰。

解题思路

一种直观的想法是先处理出关掉每一家的灯可以减少的被打扰的人家的数量，然后每次关掉可以减少被打扰人家数量最多的灯，直到被打扰的人家数量为0 。

由于数据范围很小，上面这个复杂度很高的解法依然可以通过，但事实上此题有更加优雅的解法。

稍加分析我们可以发现：每有一户被打扰的人家，必然需要关掉一盏灯，并且每关掉一盏灯，最多减少两户被打扰的人家，当且仅当a 值序列为10101 的时候，关掉中间那户人家的灯才成立。

于是我们可以发现，假设我们从左往右遍历每一户人家，假设第i 家被打扰了，那么关掉第i+1 家的灯是最优的，还可能使得第i+2 家不会被打扰。

所以，我们依照上述策略进行贪心就好了。

#include<cstdio>#include<cstring>constintMAXN=105;intn,ans;intarr[MAXN];intmain(){scanf("%d",&n);for(inti=1;i<=n;++i){scanf("%d",&arr[i]);}for(inti=2;i<n;++i){if(arr[i]==0&&arr[i-1]==1&&arr[i+1]==1){++ans;arr[i+1]=0;}}printf("%d",ans);return0;}