Switch

Time limit2sMemory limit512 MB

Summary

Given a row of K lights with no four consecutive on, find the fewest off-to-on switches needed so that all lights end up off, given the automatic clearing of any block of four or more on.

Level: Hard8 of 10
Topics: Dynamic programming, Greedy, Combinatorics
Solved: No attempts yet

Problem

You are walking past a row of $K$ lights ( $4 \le K \le 25$ ). Each light is either on or off. In the initial configuration there is no run of four or more consecutive lights that are all on.

The lights follow one rule: whenever four or more consecutive lights are on at the same time, that entire block of consecutive lit lights immediately turns off.

You may only switch a light from off to on (you can never turn a light off yourself). Turning on one light counts as a single action, and the automatic turn-off above may trigger right after any action.

Determine the minimum number of lights you must turn on so that, in the end, all $K$ lights are off.

Input

The first line contains the integer $K$ , the number of lights.

Each of the next $K$ lines contains a single integer: $0$ if that light is off, or $1$ if that light is on. The lights are given in row order.

Output

Print a single integer: the minimum number of lights you must turn on so that all $K$ lights end up off.

Examples9

Example 1
Input
```
5
1
1
0
1
1
```
Expected output
```
1
```
Example 2
Input
```
4
0
0
0
0
```
Expected output
```
0
```
Example 3
Input
```
4
1
0
0
0
```
Expected output
```
3
```
Example 4
Input
```
4
1
1
1
0
```
Expected output
```
1
```
Example 5
Input
```
4
0
1
1
0
```
Expected output
```
2
```
Example 6
Input
```
6
1
0
1
1
0
1
```
Expected output
```
4
```
Example 7
Input
```
7
1
1
0
1
1
0
1
```
Expected output
```
3
```
Example 8
Input
```
5
1
0
0
0
1
```
Expected output
```
3
```
Example 9
Input
```
7
1
1
1
0
1
1
1
```
Expected output
```
1
```