Социальная дистанция I
Новая ужасная болезнь COWVID-19 начала распространяться среди коров по всему миру. Фермер Джон старается принять как можно больше мер предосторожности, чтобы защитить свое стадо от инфекции.
Сарай фермера Джона представляет собой длинное узкое здание, в котором находятся n стойл в ряд. Некоторые из этих стойл в настоящее время заняты коровами, а некоторые пустуют. Прочитав о важности "социального дистанцирования", фермер Джон хочет максимизировать d, где d - это расстояние между двумя ближайшими занятыми стойлами. Например, если стойла 3 и 8 являются ближайшими занятыми, то d = 5.
Две новые коровы недавно присоединились к стаду фермера Джона, и ему нужно решить, в какие ранее незанятые стойла они должны быть закреплены. Определите размещение двух новых коров так, чтобы итоговое значение d было как можно большим. Фермер Джон не может перемещать ни одну из имеющихся у него коров; он только хочет выделить стойла для новых коров.
Входные данные
Первая строка содержит число n (2 ≤ n ≤ 10^5). Следующая строка содержит строку длины n из 0 и 1, описывающую последовательность стойл в сарае. 0 обозначают пустые стойла, а 1 - занятые стойла. В строке всегда имеется как минимум два 0, поэтому места для двух новых коров всегда хватит.
Выходные данные
Выведите наибольшее значение d (ближайшее расстояние между двумя занятыми стойлами), которое фермер Джон может достичь после добавления двух новых коров оптимальным образом.
Пример
Фермер Джон может добавить коров так, чтобы строка приняла вид 10x010010x0010, где x обозначает новых коров. В этом случае d = 2. Невозможно добавить новых коров для достижения более высокого значения d.