Ужасная болезнь COWVID-19 распространяется среди коров мира. Farmer John принимает максимум мер для защиты стада.
Узкий длинный амбар имеет $N$ стойл ($2 \leq N \leq 10^5$) в ряд, занятые и пустые. Узнав важность дистанции, максимизирует $D$, где $D$ — расстояние ближайших занятых. Если3 и8 ближайшие, $D = 5$.
Две новые коровы в бывшие пустые стойла, чтобы $D$ максимален. Старых двигать нельзя, лишь размещать новых.
Входные данные
Первая строка $N$, следующая01-строка длины $N$;0 пусто,1 занято. Не менее двух0, места хватает.
Выходные данные
Выведите максимальный $D$ после оптимального добавления двух, расстояние ближайших занятых.
Примеры
Входные данные 1
14 10001001000010
Выходные данные 1
2
Примечание
Можно 10x010010x0010, x новые. $D = 2$, большее $D$ невозможно.
Подзадачи
- Тесты2–6 имеют $N\le 10$.
- Тесты7–8 имеют $N\le 100$.
- Тесты9–11 имеют $N \le 5000$.
- Тесты12–15 без дополнительных условий.
Автор задачи: Brian Dean