Соціальна дистанція I#10304
Нова небезпечна хвороба COWVID-19 почала поширюватися серед корів по всьому світу. Фермер Джон намагається вжити всіх можливих заходів, щоб захистити своє стадо від інфекції.
Сарай фермера Джона — це довга вузька будівля, в якій розташовано стійл у ряд. Деякі з цих стійл зайняті коровами, а деякі залишаються порожніми. Дізнавшись про важливість "соціального дистанціювання", фермер Джон хоче максимізувати , де — це відстань між двома найближчими зайнятими стійлами. Наприклад, якщо найближчі зайняті стійла — це і , то d = 5.
Нещодавно до стада фермера Джона приєдналися дві нові корови, і йому потрібно вирішити, в які раніше незайняті стійла їх розмістити. Визначте розташування двох нових корів так, щоб підсумкове значення було якомога більшим. Фермер Джон не може переміщувати жодну з наявних корів; він лише хоче виділити стійла для нових корів.
Перша строка містить число (2 \le n \le 10^5). Наступна строка містить рядок довжини , що складається з і , який описує послідовність стійл у сараї. позначають порожні стійла, а — зайняті. У рядку завжди є принаймні два , тому місця для двох нових корів завжди вистачить.
Виведіть найбільше значення (найменша відстань між двома зайнятими стійлами), яке фермер Джон може досягти після оптимального розміщення двох нових корів.
Приклад 1
Фермер Джон може додати корів так, щоб рядок набув вигляду 10x010010x0010, де x позначає нових корів. У цьому випадку d = 2. Неможливо додати нових корів для досягнення більшого значення .