Description

Along a road, there are $n$ lights in a row; some are on, and some are off.

Dawn is about to break, and you are given a task: turn all the lights off.

However, these lights are rather smart and cannot be turned off easily. Their on/off behavior follows the rules below:

• In each step, you may turn on or off exactly one light.
• The light with index $1$ can be turned on or off freely.
• If lights $1, 2, \cdots, k-1$ are all off and light $k$ is on, then you may freely turn on or off light $k+1$.

Before turning off the lights, please compute the minimum number of steps needed to turn all the lights off.

Input Format

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

The second line contains $n$ integers. If the $i$-th integer $O_i = 0$, the $i$-th light is initially off; if $O_i = 1$, the $i$-th light is initially on.

Output Format

Output a single integer on one line, the minimum number of steps required to turn off all the lights.

4
1 0 1 0

6

Hint

[Output Explanation]

• Initial state: 1010.
• Step 1: 1110.
• Step 2: 0110.
• Step 3: 0100.
• Step 4: 1100.
• Step 5: 1000.
• Step 6: 0000.

Constraints

• For $40\%$ of the testdata, $n \le 30$.
• For $70\%$ of the testdata, $n \le 300$.
• For $100\%$ of the testdata, $n \le 1000$.

Translated by ChatGPT 5