Minimize the Infection Spread

In a country with n cities arranged in a straight line, for every 1 ≤ i < n, city i is connected with city i+1 by a bidirectional road. An epidemic has broken out. Each city is either completely infected or completely healthy. Initially, a city is infected if and only if s_i = 1 (otherwise s_i = 0).

The infection spreads in the following manner. Every morning, you may vaccinate one city that is still healthy; its residents will then become immune to infection permanently. In the afternoon, each infected city spreads the disease to its adjacent cities. Specifically, if an adjacent city has not been vaccinated that day, it becomes immediately infected and will start spreading the disease on subsequent days.

You, as the city administrator, want to minimize the total number of infected cities by applying an optimal vaccination strategy. Compute the minimum number of cities that will finally be infected.

Note on infection dynamics:
The disease spreads from each infected city to its neighbors. For a contiguous block of initially healthy cities adjacent to an infected city, if no vaccination is applied the whole block will eventually be infected. However, by vaccinating cities smartly you can block the spread. In particular, think of the healthy segments in two types:

• One‐sided segments: those attached to an infected city at one end only (for example, the beginning or the end of the line).
• Internal segments: those sandwiched between two infected cities. In these segments, the infection advances from both ends simultaneously.

An optimal strategy is to choose, each day, a healthy city in one of these segments such that you block the infection propagation in that segment. It turns out that the maximum number of cities you can save (i.e. which will never be infected) can be determined by simulating the infection front while allocating vaccinations. Suppose that if you delay vaccination, the infection will cover the segment at a rate of 1 city per day for one‐sided segments and 2 cities per day for internal segments (one from each end). Using a greedy strategy, one can calculate the total number of saved cities, and then the answer is n minus the saved cities.

For example, consider n = 5 with the initial state s = [0, 0, 1, 0, 0]. An optimal strategy will result in only 2 cities being infected at the end. See the input/output examples for more clarification.

Mathematical Formulation:
Let the positions of initially infected cities be \(a_1, a_2, \dots, a_m\). Define:

• Left one‐sided segment length: \(L = a_1 - 1\)
• Right one‐sided segment length: \(R = n - a_m\)
• Internal segment lengths: For \(1 ≤ i < m\), \(g_i = a_{i+1} - a_i - 1\).

If we simulate day by day and let d be the total days (vaccination moves) used so far, then an internal segment of length \(g\) will have an effective remaining size of \(g - 2d\). Similarly, a one‐sided segment will have an effective length \(\ell - d\). By optimally allocating vaccinations (costing 1 day for one‐sided segments and effectively 2 days for internal segments when the gap is more than 1), the total number of saved (never infected) cities can be computed. The final answer is:

[ \text{answer} = n - \text{saved}. ]

inputFormat

The first line contains a single integer n (the number of cities).

The second line contains n space‐separated integers s₁, s₂, ..., s_n, where each s_i is either 0 or 1 indicating whether the i-th city is initially healthy or infected, respectively.

outputFormat

Output a single integer: the minimum number of cities that will be infected if the vaccination strategy is chosen optimally.

sample

5
0 0 1 0 0

2