L'Olympiade internationale d'informatique aura lieu au Japon. Pour accueillir les participants du monde entier, il a été décidé de décorer les immeubles de grande hauteur situés le long de l'avenue reliant l'aéroport aux hébergements. Un célèbre designer, sollicité pour concevoir les décorations, a déclaré que les immeubles utilisés devaient être de plus en plus hauts en allant de l'aéroport vers les hébergements. Autrement dit, si leurs hauteurs, dans l'ordre en partant de l'aéroport, sont $h_1,h_2,h_3,\ldots$, il faut avoir $h_1<h_2<h_3<\cdots$.

Pour rendre les décorations aussi somptueuses que possible, on souhaite utiliser le plus grand nombre possible d'immeubles. Chargé de les choisir, JOI 君 s'est rendu compte qu'un propriétaire pourrait formuler cette demande déraisonnable : « Je veux absolument que mon immeuble soit utilisé pour les décorations. De plus, pour qu'il se remarque, je veux qu'il soit le plus proche des hébergements parmi les immeubles utilisés. »

Il y a $N$ immeubles le long de l'avenue reliant l'aéroport aux hébergements. On appelle immeuble $i$ le $i$-ième plus proche de l'aéroport ($1 \le i \le N$). Les hauteurs des $N$ immeubles sont toutes différentes. Pour être prêt à toute demande, JOI 君 a calculé à l'avance la valeur $A_i$ : le nombre maximal d'immeubles que l'on peut choisir en utilisant l'immeuble $i$ et en imposant qu'il soit le plus proche des hébergements parmi les immeubles utilisés. Il a noté la suite d'entiers $A_1,A_2,\ldots,A_N$ ainsi obtenue et l'a remise au président K du comité japonais de l'Olympiade d'informatique.

Cependant, la note reçue par le président K ne contenait en réalité qu'une suite de longueur $N-1$, notée $B_1,B_2,\ldots,B_{N-1}$. Comme il ne connaît pas les hauteurs des immeubles, il ne peut pas calculer les valeurs $A_i$.

Le président K pense que JOI 君 a certainement oublié de noter un nombre. Selon les hauteurs des immeubles, différentes suites $A_1,A_2,\ldots,A_N$ sont possibles. Parmi elles, combien donnent la suite $B_1,B_2,\ldots,B_{N-1}$ lorsqu'on en supprime une valeur ?

Il se peut toutefois que JOI 君 ait commis d'autres erreurs de transcription. Selon les valeurs de $B_1,B_2,\ldots,B_{N-1}$, il peut n'exister aucune suite de ce type.

Tâche

On vous donne une suite d'entiers $B_1,B_2,\ldots,B_{N-1}$ de longueur $N-1$. Écrivez un programme qui compte les suites possibles $A_1,A_2,\ldots,A_N$ dont on peut supprimer une valeur pour obtenir $B_1,B_2,\ldots,B_{N-1}$.

Entrée

Lisez les données suivantes sur l'entrée standard.

• La première ligne contient un entier $N$, le nombre d'immeubles situés le long de l'avenue reliant l'aéroport aux hébergements.
• La $j$-ième des $N-1$ lignes suivantes ($1 \le j \le N-1$) contient un entier $B_j$, la $j$-ième valeur de la suite figurant sur la note reçue par le président K.

Sortie

Affichez sur une ligne de la sortie standard un entier : le nombre de suites possibles $A_1,A_2,\ldots,A_N$ dont on peut supprimer une valeur pour obtenir $B_1,B_2,\ldots,B_{N-1}$.

Contraintes

Toutes les données d'entrée satisfont les conditions suivantes.

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

Sous-tâches

Sous-tâche 1 [10 points]

• $N \le 8$.

Sous-tâche 2 [30 points]

• $N \le 300$.

Sous-tâche 3 [60 points]

Aucune contrainte supplémentaire.

Exemples

Entrée 1

4
1
1
2

Sortie 1

5

Remarque

Il y a $4$ immeubles le long de l'avenue reliant l'aéroport aux hébergements. Notons $H_i$ la hauteur de l'immeuble $i$.

Selon les hauteurs des immeubles, différentes suites $A_1,A_2,A_3,A_4$ sont possibles. Parmi elles, les cinq suites suivantes donnent $1,1,2$ lorsqu'on en supprime une valeur.

• La suite $1,2,1,2$. Par exemple, si $H_2>H_4>H_1>H_3$, alors $A_1=1,A_2=2,A_3=1,A_4=2$. On obtient aussi $A_1=1,A_2=2,A_3=1,A_4=2$ si $H_2>H_1>H_4>H_3$.
• La suite $1,1,2,3$. Par exemple, si $H_4>H_3>H_1>H_2$, alors $A_1=1,A_2=1,A_3=2,A_4=3$.
• La suite $1,1,2,1$. Par exemple, si $H_3>H_1>H_2>H_4$, alors $A_1=1,A_2=1,A_3=2,A_4=1$.
• La suite $1,1,2,2$. Par exemple, si $H_3>H_4>H_1>H_2$, alors $A_1=1,A_2=1,A_3=2,A_4=2$.
• La suite $1,1,1,2$. Par exemple, si $H_4>H_1>H_2>H_3$, alors $A_1=1,A_2=1,A_3=1,A_4=2$.

Entrée 2

8
1
1
2
1
2
3
1

Sortie 2

15