Die Internationale Informatikolympiade wird in Japan stattfinden. Um die Teilnehmer aus aller Welt willkommen zu heißen, sollen die Hochhäuser entlang der Hauptstraße vom Flughafen zur Unterkunft geschmückt werden. Ein bekannter Designer wurde mit dem Entwurf beauftragt und erklärte, dass die zum Schmücken verwendeten Gebäude in Richtung vom Flughafen zur Unterkunft immer höher werden müssen. Bezeichnet man ihre Höhen, beginnend mit dem Gebäude, das dem Flughafen am nächsten liegt, mit $h_1,h_2,h_3,\ldots$, so muss also $h_1<h_2<h_3<\cdots$ gelten.

Damit der Schmuck möglichst prächtig wird, möchte man möglichst viele Gebäude dafür verwenden. JOI-kun, der mit der Auswahl der Gebäude beauftragt wurde, kam auf den Gedanken, dass ein Gebäudeeigentümer die folgende unzumutbare Forderung stellen könnte: „Mein Gebäude muss unbedingt geschmückt werden. Außerdem soll es unter den geschmückten Gebäuden der Unterkunft am nächsten liegen, damit es besonders auffällt.“

Entlang der Hauptstraße vom Flughafen zur Unterkunft stehen $N$ Gebäude. Das Gebäude, das vom Flughafen aus an $i$-ter Stelle liegt ($1 \le i \le N$), nennen wir Gebäude $i$. Die Höhen aller $N$ Gebäude sind verschieden. Um auf jede Forderung vorbereitet zu sein, berechnete JOI-kun für jedes $i$ im Voraus: „Wenn Gebäude $i$ geschmückt werden muss und unter den geschmückten Gebäuden der Unterkunft am nächsten liegen soll, beträgt die größtmögliche Anzahl auswählbarer Gebäude $A_i$.“ JOI-kun notierte die so berechnete Ganzzahlfolge $A_1,A_2,\ldots,A_N$ und übergab sie dem Vorsitzenden K des japanischen Komitees für die Informatikolympiade.

Auf dem Zettel, den der Vorsitzende K erhielt, stand jedoch tatsächlich nur eine Ganzzahlfolge $B_1,B_2,\ldots,B_{N-1}$ der Länge $N-1$. Da der Vorsitzende K die Gebäudehöhen nicht kennt, kann er die Werte $A_i$ nicht berechnen.

Der Vorsitzende K dachte, JOI-kun müsse vergessen haben, eine Zahl aufzuschreiben. Je nach Gebäudehöhen sind verschiedene Folgen $A_1,A_2,\ldots,A_N$ möglich. Wie viele dieser Folgen ergeben die Folge $B_1,B_2,\ldots,B_{N-1}$, wenn man einen Wert an einer Position entfernt?

Allerdings könnte JOI-kun beim Aufschreiben tatsächlich noch weitere Fehler gemacht haben. Je nach den Werten $B_1,B_2,\ldots,B_{N-1}$ kann es sein, dass es keine einzige solche Folge gibt.

Aufgabe

Gegeben ist eine Ganzzahlfolge $B_1,B_2,\ldots,B_{N-1}$ der Länge $N-1$. Schreibe ein Programm, das bestimmt, wie viele der möglichen Folgen $A_1,A_2,\ldots,A_N$ nach dem Entfernen eines Wertes an einer Position die Folge $B_1,B_2,\ldots,B_{N-1}$ ergeben.

Eingabe

Lies die folgenden Daten von der Standardeingabe.

• Die erste Zeile enthält eine ganze Zahl $N$. Sie gibt an, dass entlang der Hauptstraße vom Flughafen zur Unterkunft $N$ Gebäude stehen.
• Die $j$-te Zeile ($1 \le j \le N-1$) der folgenden $N-1$ Zeilen enthält eine ganze Zahl $B_j$. Sie ist der $j$-te Wert der Ganzzahlfolge auf dem Zettel, den der Vorsitzende K erhalten hat.

Ausgabe

Gib in einer Zeile auf der Standardausgabe eine ganze Zahl aus: die Anzahl der möglichen Folgen $A_1,A_2,\ldots,A_N$, die nach dem Entfernen eines Wertes an einer Position die Folge $B_1,B_2,\ldots,B_{N-1}$ ergeben.

Beschränkungen

Alle Eingabedaten erfüllen die folgenden Bedingungen.

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

Teilaufgaben

Teilaufgabe 1 [10 Punkte]

• Es gilt $N \le 8$.

Teilaufgabe 2 [30 Punkte]

• Es gilt $N \le 300$.

Teilaufgabe 3 [60 Punkte]

Es gibt keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

4
1
1
2

Ausgabe 1

5

Hinweis

Entlang der Hauptstraße vom Flughafen zur Unterkunft stehen 4 Gebäude. Die Höhe von Gebäude $i$ sei $H_i$.

Je nach Gebäudehöhen sind verschiedene Folgen $A_1,A_2,A_3,A_4$ möglich. Unter ihnen ergeben die folgenden 5 Folgen nach dem Entfernen eines Wertes an einer Position die Folge $1,1,2$.

• Die Folge $1,2,1,2$. Wenn beispielsweise $H_2>H_4>H_1>H_3$ gilt, erhält man $A_1=1,A_2=2,A_3=1,A_4=2$. Auch wenn $H_2>H_1>H_4>H_3$ gilt, erhält man $A_1=1,A_2=2,A_3=1,A_4=2$.
• Die Folge $1,1,2,3$. Wenn beispielsweise $H_4>H_3>H_1>H_2$ gilt, erhält man $A_1=1,A_2=1,A_3=2,A_4=3$.
• Die Folge $1,1,2,1$. Wenn beispielsweise $H_3>H_1>H_2>H_4$ gilt, erhält man $A_1=1,A_2=1,A_3=2,A_4=1$.
• Die Folge $1,1,2,2$. Wenn beispielsweise $H_3>H_4>H_1>H_2$ gilt, erhält man $A_1=1,A_2=1,A_3=2,A_4=2$.
• Die Folge $1,1,1,2$. Wenn beispielsweise $H_4>H_1>H_2>H_3$ gilt, erhält man $A_1=1,A_2=1,A_3=1,A_4=2$.

Eingabe 2

8
1
1
2
1
2
3
1

Ausgabe 2

15