A terrible disease afflicts the cows. Farmer John wants to protect them.
The FD Barn is a narrow long building containing N stalls in a row (2≤N≤105). Some of these stalls are already occupied by cows, some are free. After reading about the need for social distancing, the FD wants to maximize D, where D is the distance between the two closest occupied stalls. For example, if stalls 3 and 8 are the closest that are occupied, then D=5.
Two new cows have been added to FD's herd, and he must decide which unoccupied stall to place each of them in. Determine how k he should place these cows so that the result D, becomes the maximum possible. The FD cannot move any existing cows, he can only assign stalls to new cows.
Input
The first line of input contains N. The next line contains a string of length N, consisting of 0 and 1, describing the sequence of stalls in the barn. 0 means an empty stall, 1 means an occupied stall. There are at least two zeros in the string, which is enough to accommodate two cows.
Imprint
Output the largest value of D (the smallest distance between two occupied stalls) that the FD can obtain by adding two new cows in an optimal way.
Examples
| # |
Input |
Output |
|
| 1 |
14
10001001000010 |
2 |
In this example, the FD can add cows like this: 10x010010x0010 where x represents new cows. In this case D=2. It is not possible to mark cows in such a way as to get more D. |