La Olimpiada Internacional de Informática se celebrará en Japón y, para dar la bienvenida a los participantes de todo el mundo, se ha decidido decorar los edificios altos situados a lo largo de la avenida que va del aeropuerto al alojamiento. Se encargó el diseño a un famoso diseñador, quien indicó que los edificios utilizados debían aumentar de altura en dirección del aeropuerto al alojamiento. Es decir, si las alturas de los edificios elegidos, ordenados desde el más cercano al aeropuerto, son $h_1,h_2,h_3,\ldots$, debe cumplirse $h_1<h_2<h_3<\cdots$.

Para que la decoración sea lo más vistosa posible, se quiere utilizar el mayor número posible de edificios. JOI, encargado de elegirlos, se dio cuenta de que algún propietario podría hacerle una petición irrazonable: «Quiero que utilices obligatoriamente mi edificio. Además, para que destaque, quiero que sea el más cercano al alojamiento de todos los edificios utilizados».

A lo largo de la avenida entre el aeropuerto y el alojamiento hay $N$ edificios. Llamaremos edificio $i$ al $i$-ésimo más cercano al aeropuerto ($1\le i\le N$). Las alturas de los $N$ edificios son todas distintas. Para estar preparado ante cualquier petición, JOI calculó de antemano lo siguiente: «Si se eligen edificios de modo que se utilice el edificio $i$ y que este sea el más cercano al alojamiento entre los elegidos, el número máximo de edificios que se pueden elegir es $A_i$». Anotó la secuencia de enteros $A_1,A_2,\ldots,A_N$ así calculada y la entregó al presidente K del comité japonés de la Olimpiada de Informática.

Sin embargo, la nota que recibió el presidente K solo contenía una secuencia de longitud $N-1$, $B_1,B_2,\ldots,B_{N-1}$. Como no conoce las alturas de los edificios, no puede calcular los valores de $A_i$.

El presidente K pensó que JOI seguramente había olvidado escribir un número. Dependiendo de las alturas de los edificios, hay diversas secuencias posibles $A_1,A_2,\ldots,A_N$. ¿Cuántas de ellas se convierten en $B_1,B_2,\ldots,B_{N-1}$ al eliminar el valor de una posición?

Sin embargo, JOI podría haber cometido otros errores al escribir. Dependiendo de los valores de $B_1,B_2,\ldots,B_{N-1}$, puede que no exista ninguna secuencia de ese tipo.

Tarea

Se da una secuencia de enteros $B_1,B_2,\ldots,B_{N-1}$ de longitud $N-1$. Escribe un programa que cuente cuántas de las secuencias posibles $A_1,A_2,\ldots,A_N$ se convierten en $B_1,B_2,\ldots,B_{N-1}$ al eliminar el valor de una posición.

Entrada

Lee los siguientes datos de la entrada estándar.

• La primera línea contiene un entero $N$. Indica que hay $N$ edificios a lo largo de la avenida entre el aeropuerto y el alojamiento.
• La $j$-ésima línea ($1\le j\le N-1$) de las siguientes $N-1$ líneas contiene un entero $B_j$. Es el $j$-ésimo valor de la secuencia escrita en la nota que recibió el presidente K.

Salida

Escribe en una línea de la salida estándar un entero que represente el número de secuencias posibles $A_1,A_2,\ldots,A_N$ que se convierten en $B_1,B_2,\ldots,B_{N-1}$ al eliminar el valor de una posición.

Restricciones

Todos los datos de entrada satisfacen las siguientes condiciones.

• $2\le N\le1\,000\,000$.
• $1\le B_j\le N$ ($1\le j\le N-1$).

Subtareas

Subtarea 1 [10 puntos]

• $N\le8$.

Subtarea 2 [30 puntos]

• $N\le300$.

Subtarea 3 [60 puntos]

No hay restricciones adicionales.

Ejemplos

Entrada 1

4
1
1
2

Salida 1

5

Nota

Hay 4 edificios a lo largo de la avenida entre el aeropuerto y el alojamiento. Sea $H_i$ la altura del edificio $i$.

Dependiendo de las alturas de los edificios, hay distintas secuencias posibles $A_1,A_2,A_3,A_4$. Entre ellas, las que se convierten en $1,1,2$ al eliminar el valor de una posición son las cinco siguientes.

• La secuencia $1,2,1,2$. Por ejemplo, si $H_2>H_4>H_1>H_3$, se obtiene $A_1=1,A_2=2,A_3=1,A_4=2$. También se obtiene $A_1=1,A_2=2,A_3=1,A_4=2$ si $H_2>H_1>H_4>H_3$.
• La secuencia $1,1,2,3$. Por ejemplo, si $H_4>H_3>H_1>H_2$, se obtiene $A_1=1,A_2=1,A_3=2,A_4=3$.
• La secuencia $1,1,2,1$. Por ejemplo, si $H_3>H_1>H_2>H_4$, se obtiene $A_1=1,A_2=1,A_3=2,A_4=1$.
• La secuencia $1,1,2,2$. Por ejemplo, si $H_3>H_4>H_1>H_2$, se obtiene $A_1=1,A_2=1,A_3=2,A_4=2$.
• La secuencia $1,1,1,2$. Por ejemplo, si $H_4>H_1>H_2>H_3$, se obtiene $A_1=1,A_2=1,A_3=1,A_4=2$.

Entrada 2

8
1
1
2
1
2
3
1

Salida 2

15