XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: pulo.x, onde x deve ser c, cpp, java, js ou py

Pulo do Gato

O gato Obinho gosta de brincar no pátio do colégio, no qual há uma sequência de C lajotas, que podem ser brancas ou pretas. Obinho está na lajota inicial da sequência (a mais à esquerda), e quer ir pulando até a lajota final da sequência (a mais à direita). Mas ele só gosta de pular de uma lajota preta para outra lajota preta, nunca pisando numa lajota branca. Além disso, ele não consegue pular muito longe. A parte esquerda da figura mostra as lajotas que o Obinho pode alcançar com um pulo: uma distância máxima de duas lajotas.

Obinho quer chegar na lajota final com o número mínimo de pulos possível. Por exemplo, na parte direita da figura, para C=14, o menor número de pulos possível é 8. Seu programa deve computar o número mínimo de pulos para o Obinho chegar na lajota final.

Entrada

A primeira linha da entrada contém um inteiro C, representando o número de lajotas do pátio. A segunda linha contém C inteiros indicando a cor das lajotas, da inicial (mais à esquerda) à final (mais à direita): o valor 1 indica uma lajota preta, o valor 0 indica uma lajota branca.

Saída

Imprima uma linha contendo o número mínimo de pulos que o gato Obinho precisa dar para ir da lajota inicial até a lajota final. Se não for possível pular até a lajota final, imprima -1.

Restrições

  • 1 ≤ C ≤ 104;
  • As lajotas inicial e final são sempre pretas.

Informações sobre a pontuação

  • Para um conjunto de casos de teste valendo 10 pontos, todas as lajotas são pretas;
  • Para um conjunto de casos de teste valendo 20 pontos, C ≤ 1000.

Exemplos

Entrada
14
1 1 0 1 1 1 0 1 1 0 1 0 1 1
Saída
8
	

 

Entrada
14
1 0 0 1 1 1 0 0 1 0 1 1 0 1
Saída
-1
	

 

Entrada
12
1 1 1 1 1 1 1 1 1 1 1 1
Saída
6
	

 

Entrada
9
1 0 1 1 0 1 1 0 1
Saída
5
	

 

Tarefas Programação Nível Júnior
Promoção
logo sbc
Patrocínio
Apoio
Coordenação