사회적 거리두기 I

전 세계 소들 사이에서 무서운 신종 질병인 COWVID-19가 퍼지기 시작했다. 농부 존은 자신의 소 떼를 감염으로부터 보호하기 위해 가능한 한 많은 예방 조치를 취하려고 한다.

농부 존의 헛간은 $N$개의 우리가 한 줄로 늘어선 길고 좁은 건물이다($2 \leq N \leq 10^5$). 이 우리 중 일부는 소가 차 있고 일부는 비어 있다. "사회적 거리두기"의 중요성에 대해 읽은 농부 존은 $D$를 최대화하려고 한다. 여기서 $D$는 소가 있는 두 우리 사이의 최소 거리이다. 예를 들어, 소가 있는 우리 중 3번과 8번이 가장 가깝다면 $D = 5$이다.

최근 농부 존의 소 떼에 두 마리의 새 소가 합류했고, 그는 이들을 이전에 비어 있던 어느 우리에 배정할지 결정해야 한다. 두 마리의 새 소를 어떻게 배치해야 $D$ 값이 여전히 가능한 한 크게 유지되는지 구하시오. 농부 존은 기존 소를 옮길 수 없고, 새 소에게 우리를 배정하기만 하면 된다.

입력의 첫 줄에는 $N$이 주어진다. 다음 줄에는 헛간의 우리 순서를 나타내는 길이 $N$의 0과 1로 이루어진 문자열이 주어진다. 0은 빈 우리, 1은 소가 있는 우리를 나타낸다. 문자열에는 0이 적어도 두 개 있으므로 새 소 두 마리를 둘 공간은 충분하다.

농부 존이 두 마리의 새 소를 최적으로 추가한 뒤 얻을 수 있는 $D$의 최댓값(소가 있는 두 우리 사이의 최소 거리)을 출력하시오.

이 예에서 농부 존은 소를 추가해 점유 문자열이 10x010010x0010처럼 보이게 할 수 있다. 여기서 x는 새 소를 나타낸다. 이 경우 $D = 2$이다. 새 소를 추가해 $D$를 이보다 크게 만드는 것은 불가능하다.