제목: 사회적 거리두기 1

내용

새로운 심각한 질병인 소로나19가 전세계적으로 소들 사이에서 퍼지고 있다. 이 소들을 관리하는 농부 존은 소들의 감염 예방을 위해 대책을 세우고 있다.

농부 존의 목장은 길고 좁은 빌딩으로 총 N개의 칸으로 되어있다. (2 <= N <= 10^5). 일부 칸들은 이미 소들이 배치되어있고, 그 소들은 그 자리에서 움직일 수 없다. 소로나19를 예방하기 위해서 가장 좋은 대책은 "사회적 거리두기"이다. 농부 존은 D를 최대화 하려고 한다. D란, 배치된 소들 간의 가장 가까운 거리를 뜻한다. 예를 들어, 소가 3번 칸과 8번 칸에 배치되어 있다면 D는 5가 된다.

농부 존은 최근에 두 마리의 소를 더 데려왔다. D를 최대한으로 하여 2마리의 소를 추가로 배치해보자. 이미 배치되어있는 소들은 움직일 수 없고, 새로운 소들은 빈 칸에만 배치할 수 있다.

입력

첫째 줄에 목장의 크기인 N이 들어온다. 둘째 줄에 총 N개의 0과 1이 들어온다. 0은 비어있는 칸, 1은 이미 소가 배치된 칸이다. 0은 최소 2개 존재한다.

출력

D가 될 수 있는 가장 큰 값을 출력한다.

힌트

입력 예시에서 농부 존은 x가 새로운 소의 위치라고 했을 때, 10x010010x0010으로 배치할 수 있다. 이 경우 D=2가 된다. 이 D 보다 더 크게 소들을 배치할 수 없다.