Cowntact Tracing 2

면접 대비

시간 제한2초메모리 제한1024 MB

요약

매일 밤 인접한 소에게 전염되는 규칙에서 주어진 감염 비트열을 만들 수 있는 최초 감염 소의 최소 수를 구합니다.

문제

Farmer John에게는 한 줄로 서 있는 소 $N$ 마리가 있다 ( $1 \leq N \leq 3\cdot 10^5$ ). 안타깝게도 병이 무리 전체에 퍼지고 있다.

처음에는 일부 소가 감염되어 있다. 매일 밤 감염된 소는 왼쪽과 오른쪽에 있는 소(존재하는 경우)에게 병을 옮긴다. 한 번 감염된 소는 계속 감염 상태로 남는다.

며칠이 지나고 Farmer John은 상황이 통제 불능이 되었다는 것을 깨닫고, 소들을 검사해 어느 소가 병에 걸렸는지 확인한다. 처음에 감염되어 있었을 수 있는 소의 최소 마리 수를 구하라.

첫 줄에 소의 수 $N$ 이 주어진다.

다음 줄에는 길이 $N$ 이고 1과 0으로만 이루어진 이진 문자열이 주어진다. 1은 며칠 밤이 지난 뒤 감염된 소를, 0은 감염되지 않은 소를 나타낸다.

처음에 감염되어 있었을 수 있는 소의 최소 마리 수를 정수 하나로 출력한다.