Identificador: asma-t
Introducción
Hay N fichas de dominó dispuestas en círculo. Se les nombrará como dominó 0 a N-1. El i-ésimo dominó tiene el valor ai en él.
Normalmente, si se tirara una de las fichas de dominó, esto haría que el resto de las fichas de dominó se tiraran unas a otras, una por una, hasta que todas las fichas de dominó sean derribadas. Sin embargo, estas fichas no actúan como fichas de dominó normal. Estas fichas son mágicas.
Cuando la ficha i-ésima es derribada, intenta derribar al dominó numerado (i + ai) mod n (donde x mod y es igual al residuo de dividir x entre y). Sin embargo, si el dominó resultante ya ha sido eliminado, el proceso termina y no hay más fichas de dominó a derribar. En consecuencia, si empezamos con todas las fichas de dominó de pie, tenemos que escoger con cuidado que ficha de dominó derribar al inicio. Sólo algunas fichas de dominó, cuando se derriban, iniciarán una reacción en cadena como se describió anteriormente que eventualmente volteará todas las fichas de dominó. Llamaremos a estas fichas súper-dominós.
Tarea
Escribe un programa para determinar, dada N y todos los valores ai, cuántos súper-dominós hay.
Ejemplo
N = 4, a0 = 1, a1 = 3, a2 = 5, a3 = 1
Cuando se tira el dominó 2, éste tira, a su vez, al dominó 2+5 mod 4 = 3. Después, 3+1 mod 4 = 0, así que el dominó 0 es tirado. Y, 0+1 mod 4 = 1, así el dominó 1, la última ficha de dominó es tirada. El dominó 2 es por tanto un súper-dominó. Si se tira el dominó 1, sin embargo, el dominó 1+3 mod 4 = 0 es tirado. El dominó 0 trata de tirar el dominó 0+1 mod 4 = 1, que ya ha sido tirado. El proceso termina con los dominós 2 y 3 todavía en pie. Uno puede verificar que lo mismo sucede con los dominós 0 y 3. El dominó 2 es, por tanto, el único súper-dominó en este caso.
Entrada
Un entero N, seguido por N enteros correspondientes a los valores de a0 a an-1. Cada entero en una línea.
Restricciones
1 ≤ N ≤ 100000. Los valores ai son positivos.
Muestra de ejecución
Entrada
4
1
3
5
1
Salida
1
Prueba tu programa con los datos: