Соціальна дистанція 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.