무서운 COWVID-19가 세계 소에 퍼집니다. Farmer John은 감염을 막으려 최대한 예방합니다.

길고 좁은 헛간 한 줄 $N$칸 ($2 \leq N \leq 10^5$), 일부 소, 일부 비었습니다. 거리의 중요성을 읽고 $D$를 최대화합니다. $D$는 가장 가까운 사용 두 칸 거리입니다.3과8이면 $D = 5$.

새 두 소를 이전 빈 칸에 넣어 $D$ 최대화합니다. 기존 소는 못 옮기고 새 소만 배정합니다.

입력

첫 행 $N$, 다음 길이 $N$의01문자열로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