XXVI Olimpíada Brasileira de Informática
Quadradinho de 8
Fernando ficou sabendo de um novo jogo chamado quadradinho de 8. Nesse jogo, é apresentado ao jogador uma fileira de quadrados, um do lado do outro. Em cada quadrado há um número escrito. Veja abaixo um exemplo de fileira de quadrados:
Você deve estar pensando agora que Fernando quer sua ajuda para que você mostre a ele como ganhar o jogo, mas Fernando é um garoto muito esperto e sabe resolver o jogo rapidamente. Ele quer na verdade que você o ajude a descobrir de quantas formas é possível ganhar esse jogo.
Entrada
A entrada possui duas linhas. A primeira linha contém apenas um inteiro N que indica o número de quadrados na fileira de um jogo. A segunda linha contém N inteiros indicando na ordem os números presentes nos quadrados da fileira de um jogo.Saída
Seu programa deve imprimir uma única linha, contendo apenas um inteiro, o número de maneiras de ganhar o jogo apresentado na entrada. Se não for possível que o jogador ganhe o jogo, imprima 0.Restrições
- 1 ≤ N ≤ 1000000
- Os números nos quadrados são inteiros não negativos menores ou iguais a 1000.
Informações sobre a pontuação
- Para um conjunto de entradas totalizando 50 pontos, N ≤ 200
- Para um conjunto de entradas totalizando 70 pontos, N ≤ 5000
Exemplos
Entrada
6 3 4 6 0 2 9 |
Saída
3 |
Entrada
7 1 1 1 1 1 1 1 |
Saída
0 |
Entrada
5 8 0 8 0 8 |
Saída
15 |