Description

Xiao Z, a friend of zhouwc (the “my friend is actually me” kind), cannot bear the hunger and has to take the risk of ordering delivery.

However, to catch students who order delivery, Director Q set up a tight net—cameras.

But because the school’s budget for Director Q is limited, these cameras cannot work continuously. After working for one second, they must stop and rest for one second, that is, after being on for one second, they turn off for one second, then on for one second... and so on.

Also due to limited budget, these cameras are arranged in a straight line, which lies on the only path students must take to reach the delivery pickup point—the Gate 2 (with no guard).

Because Xiao Z has learned a sprint skill, the time for him to pass through any number of cameras that are turned off is $1$ (that is, in one move he can pass through several cameras that are not on).

Since Xiao Z wants to eat delivery food but does not want to be punished by Director Q watching in the control room, please tell him the minimum time needed to safely reach the pickup point.

Input Format

There are $2$ lines in total.

The first line contains a positive integer $n$, meaning there are $n$ cameras on this road.

The second line contains $n$ numbers, representing the on/off states of these cameras at time $0$ seconds. $0$ means a camera is off, and $1$ means it is on. It is guaranteed that the first camera is off.

Output Format

Output one line, the time required for Xiao Z to safely reach the delivery pickup point.

6
0 0 1 1 0 1

4

6
0 0 0 0 0 0

1

Hint

Constraints

For $10\%$ of the testdata, $1 \leq n \leq 10$.

For $30\%$ of the testdata, $1 \leq n \leq 100$.

For $50\%$ of the testdata, $1 \leq n \leq 10^3$.

For $70\%$ of the testdata, $1 \leq n \leq 10^5$.

For $100\%$ of the testdata, $1 \leq n \leq 10^6$.

The camera states are all represented using $0$ and $1$.

Sample Explanation 1

In the first second, Xiao Z rushes to the second camera, taking $1$ second, for a total time of $1$ second.

In the second second, the camera states become $1\ 1\ 0\ 0\ 1\ 0$.

At this time, Xiao Z quickly rushes from the second camera to the fourth camera, taking $1$ second, for a total time of $2$ seconds.

In the third second, the camera states become $0\ 0\ 1\ 1\ 0\ 1$.

At this time, Xiao Z quickly rushes from the fourth camera to the fifth camera, taking $1$ second, for a total time of $3$ seconds.

In the fourth second, the camera states become $1\ 1\ 0\ 0\ 1\ 0$.

At this time, Xiao Z quickly rushes from the fifth camera and leaves the monitored area, taking $1$ second, for a total time of $4$ seconds.

Sample Explanation 2

In the first second, Xiao Z rushes out of the monitored area directly.

Translated by ChatGPT 5