Le Olimpiadi Internazionali di Informatica si tengono in Giappone. Per dare il benvenuto agli atleti provenienti da tutto il mondo, è stato deciso di decorare i grattacieli lungo la strada principale che va dall'aeroporto alla struttura ricettiva. Il progetto è stato commissionato a un famoso designer, il quale ha stabilito che gli edifici utilizzati per la decorazione devono aumentare di altezza procedendo dall'aeroporto verso la struttura ricettiva. In altre parole, se indichiamo le altezze degli edifici utilizzati per la decorazione in ordine a partire da quello più vicino all'aeroporto come $h_1, h_2, h_3, \dots$, allora deve valere $h_1 < h_2 < h_3 < \dots$.

Per rendere le decorazioni il più spettacolari possibile, vogliamo utilizzare il maggior numero possibile di edifici. JOI, che è stato incaricato di selezionare gli edifici da decorare, si è reso conto che esiste la possibilità che il proprietario di un edificio faccia la richiesta irragionevole: "Voglio che usiate assolutamente il mio edificio per la decorazione. Inoltre, per far risaltare l'edificio, voglio che scegliate gli edifici in modo tale che il mio edificio sia quello più vicino alla struttura ricettiva tra tutti gli edifici utilizzati per la decorazione."

Ci sono $N$ edifici lungo la strada principale dall'aeroporto alla struttura ricettiva, e chiamiamo l'$i$-esimo edificio dall'aeroporto ($1 \le i \le N$) edificio $i$. Le altezze degli $N$ edifici sono tutte distinte. JOI ha precalcolato quanto segue: "Quando si scelgono gli edifici in modo che l'edificio $i$ sia utilizzato per la decorazione e l'edificio $i$ sia quello più vicino alla struttura ricettiva tra tutti gli edifici utilizzati per la decorazione, il numero massimo di edifici che possono essere scelti è $A_i$."

JOI ha annotato la sequenza di interi $A_1, A_2, \dots, A_N$ calcolata in questo modo e l'ha consegnata al Presidente K del Comitato Giapponese per le Olimpiadi Internazionali di Informatica.

Tuttavia, l'appunto che il Presidente K ha ricevuto conteneva in realtà solo una sequenza di interi $B_1, B_2, \dots, B_{N-1}$ di lunghezza $N-1$. Poiché il Presidente K non conosce le informazioni sulle altezze degli edifici, non può calcolare i valori di $A_i$.

Il Presidente K ha pensato che JOI dovesse aver dimenticato di trascrivere un numero. Si possono considerare varie sequenze $A_1, A_2, \dots, A_N$ a seconda delle altezze degli edifici. Tra queste, quante sono le sequenze tali che rimuovendo un valore dalla sequenza si ottiene la sequenza $B_1, B_2, \dots, B_{N-1}$?

Si noti che, in realtà, JOI potrebbe aver commesso altri errori nello scrivere. A seconda dei valori di $B_1, B_2, \dots, B_{N-1}$, potrebbe non esistere alcuna sequenza di questo tipo.

Compito

Data una sequenza di interi $B_1, B_2, \dots, B_{N-1}$ di lunghezza $N-1$, scrivi un programma per determinare quante sequenze $A_1, A_2, \dots, A_N$ possono essere considerate tali che rimuovendo un valore dalla sequenza si ottenga la sequenza $B_1, B_2, \dots, B_{N-1}$.

Input

Leggi quanto segue dallo standard input:

• La prima riga contiene un intero $N$. Questo rappresenta il fatto che ci sono $N$ edifici lungo la strada principale dall'aeroporto alla struttura ricettiva.
• La $j$-esima riga ($1 \le j \le N-1$) delle successive $N-1$ righe contiene un intero $B_j$. Questo è il $j$-esimo valore della sequenza di interi scritta nell'appunto ricevuto dal Presidente K.

Output

Stampa in una singola riga l'intero che rappresenta il numero di sequenze $A_1, A_2, \dots, A_N$ tali che rimuovendo un valore dalla sequenza si ottiene la sequenza $B_1, B_2, \dots, B_{N-1}$.

Limiti

Tutti i dati di input soddisfano le seguenti condizioni:

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

Sottoproblemi

1. (10 punti) Vale $N \le 8$.
2. (30 punti) Vale $N \le 300$.
3. (60 punti) Nessun limite aggiuntivo.

Esempi

Input 1

4
1
1
2

Output 1

5

Ci sono 4 edifici lungo la strada principale dall'aeroporto alla struttura ricettiva. Sia $H_i$ l'altezza dell'edificio $i$. Si possono considerare varie sequenze $A_1, A_2, A_3, A_4$ a seconda delle altezze degli edifici. Tra queste, ci sono 5 modi tali che rimuovendo un valore dalla sequenza si ottiene la sequenza $1, 1, 2$:

• Sequenza $1, 2, 1, 2$. Ad esempio, quando $H_2 > H_4 > H_1 > H_3$, abbiamo $A_1 = 1, A_2 = 2, A_3 = 1, A_4 = 2$. Inoltre, quando $H_2 > H_1 > H_4 > H_3$, abbiamo $A_1 = 1, A_2 = 2, A_3 = 1, A_4 = 2$.
• Sequenza $1, 1, 2, 3$. Ad esempio, quando $H_4 > H_3 > H_1 > H_2$, abbiamo $A_1 = 1, A_2 = 1, A_3 = 2, A_4 = 3$.
• Sequenza $1, 1, 2, 1$. Ad esempio, quando $H_3 > H_1 > H_2 > H_4$, abbiamo $A_1 = 1, A_2 = 1, A_3 = 2, A_4 = 1$.
• Sequenza $1, 1, 2, 2$. Ad esempio, quando $H_3 > H_4 > H_1 > H_2$, abbiamo $A_1 = 1, A_2 = 1, A_3 = 2, A_4 = 2$.
• Sequenza $1, 1, 1, 2$. Ad esempio, quando $H_4 > H_1 > H_2 > H_3$, abbiamo $A_1 = 1, A_2 = 1, A_3 = 1, A_4 = 2$.

Input 2

8
1
1
2
1
2
3
1

Output 2

15