P5639 [CSGRound2] The Dignity of the Lawful Ones

Because School Y recently carried out a full reform of the school cafeteria and a complete “cleanup” (messing around) of the school store, the snacks sold in the school store were banned; the fried chicken stall in the cafeteria also disappeared. Also, Director Q from the Student Affairs Office strictly forbids students from ordering delivery, monitoring day and night. As the saying goes, food is the first necessity of the people. Since they are hungry all day, students across the whole school are suffering badly.

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.

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 one line, the time required for Xiao Z to safely reach the delivery pickup point.

#### 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