En la Isla de los Truhanes y Caballeros los caballeros siempre dicen la verdad, los truhanes siempre mienten y ningún habitante de la Isla es truhán o caballero a la vez. Se han escapado algunos truhanes de la prisión y la policía ha contratado al Inspector Craig para encontrar a los fugitivos.

Hay ~n~ habitantes en la Isla, de ellos se saben que hay exactamente ~3~ truhanes y ~n-3~ caballeros. Inicialmente cada habitante sabe su rol (truhán o caballero). Además, cada truhán conoce perfectamente a los demás truhanes, pero los caballeros no tienen ninguna información adicional sobre el rol de los demás habitantes.

El Inspector Craig organizó un interrogatorio donde cada habitante acusa a otro de ser truhán. Por supuesto, los truhanes siempre dicen mentira por tanto nunca acusarán a otro truhán, sin embargo un caballero puede acusar o a un truhán o a un caballero (puede equivocarse en su acusación). Dado el resultado del interrogatorio el Inspector Craig se pregunta de cuántas formas es posible seleccionar qué habitantes son truhanes.

Subtareas

• Subtarea 1 (23 puntos): ~3 \le n \le 100~
• Subtarea 2 (24 puntos): ~3 \le n \le 5000~
• Subtarea 3 (53 puntos): ~3 \le n \le 10^5~

Entrada

La primera línea de la entrada contiene un entero ~n~: el número de habitantes de la Isla. Los habitantes están numerados ~1, 2, \dots, n~.

La segunda línea de la entrada contiene ~n~ enteros ~x_1, x_2, \dots, x_n~, donde ~x_k~ es el habitante al que el habitante ~k~ acusa de ser una truhán.

Salida

Debes imprimir un número entero: la cantidad de formas de seleccionar qué habitantes son los truhanes.

Ejemplos

Entrada 1

6
2 5 4 1 4 5

Salida 1

4

Los truhanes pueden ser ~(1,3,5)~, ~(1,3,6)~, ~(2,3,6)~ o ~(2,4,6)~.