토네이도!

이상 기후가 우리 지역을 점점 더 자주 강타하고 있습니다. 방금 토네이도가 소와 우유를 생산하는 실버라도 농장(Silverado Farm)을 덮쳐 큰 피해를 남겼습니다. 헛간 지붕이 뜯겨 나가고, 여러 그루의 나무가 뿌리째 뽑혔으며, 농장 트럭이 뒤집혔습니다. 무엇보다도 토네이도는 농장을 둘러싼 울타리의 여러 구간을 파괴했습니다.

이 울타리는 아주 튼튼하게 지어졌습니다. 콘크리트 기둥이 $2$미터마다 세워져 있고 철조망으로 연결되어 농장의 둘레 전체를 감쌉니다. 둘레(미터 단위)는 짝수이므로 기둥은 완벽하게 규칙적으로 배치되어 있습니다. 울타리는 하나의 닫힌 고리 형태이므로 마지막 기둥은 첫 번째 기둥과 맞닿아 있습니다.

토네이도로 일부 기둥이 부러지거나 쓰러져 울타리에 빈틈이 생겼습니다. 소가 빠져나가지 못하도록 농장 주인은 나무 기둥으로 빈틈을 임시로 막으려 합니다. 나무 기둥은 부러지거나 사라진 콘크리트 기둥이 있던 바로 그 자리에만 세울 수 있습니다. 임시 복구를 더 빠르고 저렴하게 하기 위해, 주인은 서로 이웃한 두 기둥(콘크리트든 나무든) 사이의 철조망 길이가 항상 $4$미터를 넘지 않도록 유지하면서도 나무 기둥을 가능한 한 적게 사용하려고 합니다.

어떤 기둥이 남아 있고 어떤 기둥이 부러지거나 사라졌는지가 주어질 때, 모든 빈틈을 막는 데 필요한 나무 기둥의 최소 개수를 구하세요.

입력은 여러 개의 테스트 케이스로 이루어지며 파일의 끝까지 계속됩니다. 각 테스트 케이스는 두 줄로 주어집니다.

첫 번째 줄에는 원래 울타리에 있던 콘크리트 기둥의 개수 $N$이 주어집니다 ($5 \le N \le 5000$).

두 번째 줄에는 토네이도 이후 각 기둥의 상태를 나타내는 $N$개의 정수 $X_1, X_2, \dots, X_N$이 주어집니다 ($0 \le X_i \le 1$). $X_i = 1$이면 기둥 $i$는 온전한 상태이고, $X_i = 0$이면 기둥 $i$는 부러졌거나 사라진 것입니다. 울타리는 닫힌 고리이므로 기둥 $X_N$은 기둥 $X_1$과 이웃합니다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력합니다: 주인의 규칙에 따라 울타리를 복구하는 데 필요한 나무 기둥의 최소 개수.