스위치

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

요약

켜진 등이 네 개 이상 연속하지 않는 초기 상태에서, 네 개 이상 연속으로 켜지면 그 블록이 자동으로 꺼지는 규칙 아래 모든 등을 끄는 데 필요한 최소 스위치 횟수를 구한다.

문제

한 줄로 놓인 $K$ 개( $4 \le K \le 25$ )의 전구 옆을 지나가고 있습니다. 각 전구는 켜져 있거나 꺼져 있습니다. 처음 상태에서는 연속으로 켜진 전구가 4개 이상인 구간이 존재하지 않습니다.

전구에는 한 가지 규칙이 있습니다. 어느 순간이든 연속으로 켜진 전구가 4개 이상이 되면, 그 연속된 구간의 전구들이 즉시 모두 꺼집니다.

당신은 꺼져 있는 전구만 켤 수 있습니다(전구를 직접 끌 수는 없습니다). 전구 하나를 켜는 것을 한 번의 동작으로 세며, 위의 자동 꺼짐은 각 동작 직후에 일어날 수 있습니다.

모든 $K$ 개의 전구를 최종적으로 꺼진 상태로 만들기 위해 켜야 하는 전구의 최소 개수를 구하세요.

첫째 줄에 전구의 개수 $K$ 가 주어집니다.

다음 $K$ 개의 줄에는 각각 정수 하나가 주어지며, 해당 전구가 꺼져 있으면 $0$ , 켜져 있으면 $1$ 입니다. 전구는 줄에 놓인 순서대로 주어집니다.

모든 $K$ 개의 전구를 꺼진 상태로 만들기 위해 켜야 하는 전구의 최소 개수를 정수 하나로 출력하세요.