The Light Switch Duel

There are n lights in a row. The initial state is given by a sequence \(a_1, a_2, \dots, a_n\), where each \(a_i\) is either 0 (off) or 1 (on).

From the morning of the first day onward, the Demon King and the Hero take turns as follows:

• Morning (Demon King): He selects two consecutive lights (i.e. positions \(i\) and \(i+1\) for some valid \(i\)) and sets both of them to 0. He may choose any pair regardless of their current state.
• Evening (Hero): He may select up to three arbitrary lights and set them to 1. (There is no restriction on whether these positions are consecutive.)

The process is repeated day by day. The Hero’s goal is to eventually have all lights turned on (i.e. state 1 for every light) immediately after one of his moves – that is, before the Demon King can act the next morning. Both players play optimally: the Demon King seeks to delay the completion as long as possible, while the Hero aims to finish in as few days (i.e. Hero’s moves) as possible.

Game details and a key observation:

The Demon King’s move is restricted to flipping a pair of consecutive lights to 0. Note that if the current configuration contains two or more 1’s that are adjacent it is possible for him to remove 2 ones in one move. However, the Hero may try to arrange his choices so that, before his move, the 1’s are isolated, in which case the Demon King can remove at most 1 one. Nevertheless, since eventually the Hero must turn on all lights (even if that creates adjacent ones), in the worst‐case the Demon King can force the net increase (in the number of lights on) per full day to be as little as 1 (or even 0 when all lights are already on).

An analysis of optimal play shows that if we let \(p\) be the number of lights that are on in the initial configuration and assume both players play optimally, then the minimum number of days (i.e. the number of Hero’s moves) required is determined as follows:

• If \(n = 1\):
  • If the only light is already on (\(p = 1\)), the answer is 0.
  • If it is off (\(p = 0\)), the Hero simply turns it on, so the answer is 1.
• If \(n \ge 2\):
  • If the configuration is already complete (i.e. \(p = n\)) the answer is 0.
  • If \(p \ge 2\) (i.e. at least 2 lights are on initially), the Demon King, by his optimal play, can force a situation in which each full day increases the count of on lights by exactly 1 before the Hero’s move. Hence the answer is n - p.
  • If \(p < 2\) (i.e. \(p = 0\) or \(p = 1\)), then due to the Demon King’s ability to disrupt the sparse on lights, analysis shows that the minimum number of days required is n - 2 (with the understanding that for small \(n\) the result is adjusted to at least 1 move).

In summary, if we denote the answer by days then the answer can be computed as follows (for \(n \ge 2\)):

[ \text{days} = \begin{cases} 0, & \text{if } p=n;\ n - p, & \text{if } p \ge 2;\ n - 2, & \text{if } p < 2. \end{cases} ]

For \(n=1\), the answer is 0 if \(p=1\) and 1 if \(p=0\).

You are to write a program to compute the minimum number of days needed for the Hero to have all lights turned on.

inputFormat

The first line contains a single integer \(n\) (\(1 \le n \le 10^5\)), the number of lights.

The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\), each of which is either 0 or 1, representing the initial state of each light.

outputFormat

Output a single integer — the minimum number of days (Hero’s moves) required to have all the lights turned on.

sample

1
0

1