Encontros com uma Pausa
Em uma rede de entregas existem estações. De cada estação sai exatamente uma estrada de sentido único, que leva à estação . Uma viagem por qualquer estrada leva exatamente um minuto. Algumas estações são pontos de descanso.
Dois entregadores começam simultaneamente em duas estações distintas. A cada minuto, cada um segue a estrada que sai da estação onde está. Opcionalmente, cada entregador pode, no máximo uma vez durante toda a viagem, gastar um minuto inteiro parado em uma estação de descanso, em vez de percorrer sua estrada naquele minuto. As decisões dos dois entregadores são independentes.
Dizemos que as duas estações iniciais são compatíveis se for possível planejar essas pausas de modo que, em algum instante inteiro , os entregadores estejam na mesma estação.
Conte a quantidade de pares não ordenados de estações iniciais distintas que são compatíveis.
Input
A primeira linha contém .
A segunda linha contém inteiros ; é permitido .
Output
Imprima a quantidade de pares não ordenados de estações iniciais distintas que podem se encontrar.
Samples
Sample 1
Input
2 2 1 0 0
Output
0
Os dois entregadores caminham em sentidos sincronizados ao longo do ciclo de comprimento 2 e nunca coincidem.
Sample 2
Input
2 2 1 1 0
Output
1
O entregador que começa na estação 1 pode esperar um minuto enquanto o outro se desloca da estação 2 à estação 1.
Sample 3
Input
3 2 3 3 0 0 0
Output
3
Todos os caminhos chegam à estação 3, que possui um laço; todo par acaba se encontrando.