Illumination 2

Interview

Time limit2sMemory limit1024 MB

Summary

You may turn on a prefix of the bulbs once, then flip individual bulbs; find the minimum number of flips to reach the target pattern.

Level: Easy3 of 10
Topics: Prefix sum, Greedy, Array, Implementation
Solved: No attempts yet

Problem

Aoi, a student at JOI High School, decided to decorate a hallway with lights for the school festival.

The decoration consists of N light bulbs arranged in a line running east to west. The bulbs are numbered 1 through N from the west side. Each bulb has two states, on and off, and initially all bulbs are off.

The pattern Aoi wants is given by a sequence A1, A2, ..., AN: when Ai = 1, bulb i should be on, and when Ai = 0, it should be off. Aoi wants to reach this pattern in as little time as possible.

Aoi may first perform the following operation exactly once, or not at all.

Turn on the bulbs in a contiguous segment starting from the west end. That is, choose one integer r with 1 ≤ r ≤ N and turn on bulbs 1, 2, ..., r.

The time this operation takes is negligible.

After that, Aoi may perform the following operation any number of times.

Choose one bulb and change its state (on becomes off, off becomes on).

This operation takes 1 minute each time.

Given the number of bulbs and the target pattern, write a program that finds the minimum number of minutes Aoi needs to reach the target pattern.

Input

The input is given from standard input in the following format.

N
A1 A2 … AN

Output

Print the minimum number of minutes needed to reach the target pattern on one line to standard output.

Constraints

1 ≦ N ≦ 200 000.
Ai is either 0 or 1 (1 ≦ i ≦ N).
All input values are integers.

Examples4

Example 1
Input
```
6
0 1 1 0 0 1
```
Expected output
```
2
```
Example 2
Input
```
4
0 0 0 1
```
Expected output
```
1
```
Example 3
Input
```
4
1 1 1 1
```
Expected output
```
0
```
Example 4
Input
```
15
1 0 0 0 0 1 1 1 0 1 0 0 1 0 1
```
Expected output
```
6
```