Escape Room

Time limit1sMemory limit256 MB

Summary

Each press toggles one button and up to two buttons to its right; find the fewest presses to turn an all-off row of N lights into a target 0/1 pattern.

Level: Medium6 of 10
Topics: Greedy, Array, Bit manipulation, Implementation
Solved: No attempts yet

Problem

Hyemin is playing an escape room game and has reached the last puzzle. The clues are these.

N buttons stand in a row in front of her, and every light is off at the start.
A note carries an N-digit number written with only 0 and 1.
A 0 means a button whose light is off, and a 1 means a button whose light is on.
Pressing a lit button turns its light off, and pressing an unlit button turns its light on.
Pressing a button also presses the two neighboring buttons to its right. When fewer than two buttons remain on the right, only the buttons that exist are pressed.

Starting from the state where every light is off, Hyemin has to press buttons the fewest possible times to reach exactly the state written on the note. Help her escape the room.

Input

The first line contains N. ( $1 \le N \le 1{,}000{,}000$ )

The second line contains the N-digit number on the note, one digit at a time, separated by spaces.

Output

Print the minimum number of button presses that reaches the state written on the note.

Hint

When $N = 7$ and the note reads 0 0 1 0 0 1 0, two presses build that state.

the starting state with every light off → 0 0 0 0 0 0 0
after pressing the third button → 0 0 1 1 1 0 0
after pressing the fourth button → 0 0 1 0 0 1 0

Examples4

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