Новая ужасная болезнь 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.