시안화물 강

화성 남극 빙상에서 흘러나오는 시안화물 강은 독성 물질 때문에 매우 위험하며, 강에 가까이서 하는 작업은 대개 극도로 오래 걸린다.

화성 온난화 이후 강이 나타나기 전에 이 지역에는 통신탑들이 한 줄로 세워졌다.

지금은 일부 탑이 강에 직접 서 있고, 나머지는 강 밖이나 강기슭, 또는 강에 있는 섬에 서 있다. 줄의 첫 번째 탑과 마지막 탑은 강기슭에 서 있다.

현재의 어려운 조건에서 다음 운영 기간을 위해 모든 탑을 공식적으로 인증해야 한다.

강기슭이나 섬에 서 있는 탑은 즉시 인증할 수 있다. 강에 있는 탑에 접근하는 것은 위험하며 각별한 주의가 필요하다. 강에 서 있는 탑 하나를 인증하는 데는 하루가 걸린다. 또한 강에 서 있는 탑은 인접한 탑 중 적어도 하나가 최소 하루 전에 인증된 경우에만 인증할 수 있다. 다행히 인증 작업은 탑마다 독립적으로 수행할 수 있으므로 하루에 여러 탑을 인증할 수 있다.

인증 작업은 가능한 한 빨리 끝내야 한다.

입력은 앞에 0이 없고 최대 300 000자리인 홀수 이진수 한 줄로 이루어진다. 각 자릿수는 탑 하나를 나타낸다. 강에 서 있는 탑은 0, 나머지 탑은 1로 나타낸다. 자릿수의 순서는 줄에 있는 탑의 순서와 같다.

모든 탑을 인증할 수 있는 최소 일수를 출력한다.