Tornado!

Interview

Time limit1sMemory limit128 MB

Summary

Given a circular fence of N posts marked standing or broken, choose the fewest broken posts to fill so no wire span between standing posts exceeds 4 meters.

Level: Medium4 of 10
Topics: Greedy, Array, Implementation, Simulation
Solved: No attempts yet

Problem

Extreme weather has been striking our region more and more often. A tornado has just hit Silverado Farm — a cattle and milk producer — and left a trail of destruction: the barn roof was torn off, several trees were uprooted, and the farm truck was flipped over. Worst of all, the tornado destroyed several sections of the fence that surrounds the property.

The fence was very well built. Concrete posts stand every $2$ meters and are connected by barbed wire, enclosing the entire perimeter of the farm. The perimeter (in meters) is an even number, so the posts are perfectly regular. The fence is a closed loop: the last post is adjacent to the first one.

The tornado broke or knocked down some of the posts, leaving gaps in the fence. To keep the cattle from escaping, the owners will temporarily close the gaps with wooden posts. A wooden post may be placed only at the exact spot where a broken or missing concrete post used to stand. To make the temporary repair faster and cheaper, the owners want to use as few wooden posts as possible, while still keeping every stretch of barbed wire between two consecutive standing posts (concrete or wooden) at most $4$ meters long.

Given which posts are still standing and which are broken or missing, determine the minimum number of wooden posts needed to close all the gaps.

Input

The input contains several test cases and ends at end of file. Each test case is given on two lines.

The first line contains an integer $N$ , the number of concrete posts in the original fence ( $5 \le N \le 5000$ ).

The second line contains $N$ integers $X_1, X_2, \dots, X_N$ describing the state of each post after the tornado ( $0 \le X_i \le 1$ ). If $X_i = 1$ , post $i$ is still in good condition; if $X_i = 0$ , post $i$ is broken or missing. The fence is a closed loop, so post $X_N$ is adjacent to post $X_1$ .

Output

For each test case, print a single line with one integer: the minimum number of wooden posts needed to restore the fence following the owners' rule.

Examples2

Example 1

Input

10
1 0 0 1 0 0 1 0 1 1
11
1 0 0 1 0 0 0 1 1 0 1
12
0 0 0 0 0 1 1 0 0 0 1 1

Expected output

2
2
3

Example 2
Input
```
5
1 1 1 1 1
```
Expected output
```
0
```