Problem Description

A new disease, COWVID-19, has begun spreading among cows around the world. Farmer John is taking as many precautions as possible to prevent his herd from being infected.

Farmer John's barn is a long, narrow building with a row of $N$ stalls ($2\le N\le 10^5$). Some stalls currently contain cows, and some are currently empty. Knowing the importance of "social distancing", Farmer John wants to make $D$ as large as possible, where $D$ is the distance between the two closest occupied stalls. For example, if stalls $3$ and $8$ are the closest occupied stalls, then $D=5$.

Two new cows have just arrived in Farmer John's herd, and he needs to decide which two previously empty stalls to assign them to. Please determine how to place these two new cows so that $D$ is still as large as possible. Farmer John cannot move any existing cows; he only wants to assign stalls to the new cows.

Input Format

The first line of input contains $N$. The next line contains a string of length $N$ consisting of $0$ and $1$, describing the stalls in the barn. $0$ means an empty stall, and $1$ means an occupied stall. The string contains at least two $0$ characters, so there is enough space to place the two new cows.

Output Format

Output the maximum value of $D$ (the distance between the closest occupied stalls) that Farmer John can achieve after adding the two new cows in the optimal way.

14
10001001000010

2

Hint

Sample Explanation 1

In this example, Farmer John can add cows so that the stall assignment becomes 10x010010x0010, where x represents a new cow. Then $D=2$. It is not possible to achieve a larger value of $D$ after adding the cows.

Test Point Properties

• Test points $2-6$ satisfy $N\le 10$.
• Test points $7-8$ satisfy $N\le 100$.
• Test points $9-11$ satisfy $N\le 5000$.
• Test points $12-15$ have no additional constraints.

Translated by ChatGPT 5