Problem Description

Aoi, a student at JOI High School, has decided to decorate the corridor with illumination for the school festival.

The illumination is made by arranging $ N $ bulbs in a straight line from west to east. The bulbs are numbered from 1 to $ N $ starting from the west side. Each bulb has two states: on and off. Initially, all bulbs are off.

Aoi's desired pattern for the illumination is represented by the sequence $A_1, A_2, \ldots, A_N$, where $ A_i = 1 $ means bulb $ i $ should be on, and $ A_i = 0 $ means it should be off. Aoi wants to achieve this pattern in the shortest possible time.

Aoi can perform the following operation once initially, but it is optional:

• Turn on a contiguous segment of bulbs starting from the west end. That is, choose an integer $ r $ between 1 and $ N $, and turn on bulbs $1, 2, \ldots, r$.

The time taken for this operation is negligible.

After that, Aoi can perform the following operation any number of times:

• Change the state of a single bulb (from on to off, or from off to on).

Each execution of this operation takes 1 minute.

Given the number of bulbs and the desired pattern, write a program to determine the minimum number of minutes Aoi needs to achieve the target pattern.

Input Format

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

$ N $ $ A_1 $ $ A_2 $ $\cdots$ $ A_N $

Output Format

Output to the standard output the minimum number of minutes required to achieve the target pattern in one line.

Sample Input and Output

Sample Input #1

6
0 1 1 0 0 1

Sample Output #1

2

Sample Input #2

4
0 0 0 1

Sample Output #2

1

Sample Input #3

4
1 1 1 1

Sample Output #3

0

Sample Input #4

15
1 0 0 0 0 1 1 1 0 1 0 0 1 0 1

Sample Output #4

6

Notes/Hints

Constraints

• $1 \leq N \leq 200,000$.
• $ A_i $ is either 0 or 1 (for $1 \leq i \leq N$).
• All values input are integers.

Subtasks

1. (45 points) $N \leq 2,000$.
2. (55 points) No additional constraints.

Grading Notes

All submissions are graded on the judge system.

A submitted source code is considered correct for a subtask if it returns the correct result for all test inputs corresponding to that subtask.

The score for each submission is the sum of the points for the subtasks it correctly solves.

The score for this task is the maximum score of all submissions for this task.

The current score can be checked under the "My Score Status" tab in the "Submission Results".

Sample Explanation 1

For example, Aoi could initially choose $ r = 3 $ to turn on bulbs $ 1, 2, 3 $. This operation takes 0 minutes. Then, change the state of bulb $ 1 $ from on to off and bulb $ 6 $ from off to on. Each of these operations takes 1 minute, totaling 2 minutes. It is not possible to achieve the target pattern in less than 2 minutes, so output 2.

Sample Explanation 2

In this input example, Aoi does not perform the initial operation. Then, change the state of bulb $ 4 $ from off to on. This operation takes 1 minute, and it is not possible to achieve the target pattern in less than 1 minute, so output 1.

Sample Explanation 3

In this input example, Aoi could initially choose $ r = 4 $ to turn on bulbs $ 1, 2, 3, 4 $. This operation takes 0 minutes, so output 0.

见题面 Input 部分

见题面 Output 部分