Den internasjonale informatikkolympiaden arrangeres i Japan. For å ønske deltakerne fra hele verden velkommen er det bestemt at skyskraperne langs hovedgaten fra flyplassen til overnattingsstedet skal dekoreres. En kjent designer fikk i oppdrag å utforme designet, og vedkommende uttalte at bygningene som brukes til dekorasjon må øke i høyde fra flyplassen mot overnattingsstedet. Med andre ord, hvis vi betegner høydene på bygningene som brukes til dekorasjon i rekkefølge fra den som ligger nærmest flyplassen som $h_1, h_2, h_3, \dots$, så må det gjelde at $h_1 < h_2 < h_3 < \dots$.

For å gjøre dekorasjonene så spektakulære som mulig ønsker vi å bruke så mange bygninger som mulig. JOI, som fikk i oppgave å velge ut bygningene som skulle dekoreres, innså at det er en mulighet for at en bygningseier kan komme med det urimelige kravet: "Jeg vil at dere absolutt skal bruke bygningen min til dekorasjon. For å få bygningen til å skille seg ut vil jeg dessuten at dere skal velge bygningene slik at bygningen min er den som ligger nærmest overnattingsstedet blant alle bygningene som brukes til dekorasjon."

Det er $N$ bygninger langs hovedgaten fra flyplassen til overnattingsstedet, og vi kaller den $i$-te bygningen fra flyplassen ($1 \le i \le N$) for bygning $i$. Høydene på de $N$ bygningene er alle forskjellige. JOI har på forhånd beregnet følgende: "Når man velger bygninger slik at bygning $i$ brukes til dekorasjon og bygning $i$ er den som ligger nærmest overnattingsstedet blant alle bygninger som brukes til dekorasjon, er det maksimale antallet bygninger som kan velges $A_i$."

JOI noterte ned heltallsfølgen $A_1, A_2, \dots, A_N$ beregnet på denne måten og leverte den til styreleder K i den japanske komiteen for Den internasjonale informatikkolympiaden.

Notatet som styreleder K mottok, inneholdt imidlertid faktisk bare en heltallsfølge $B_1, B_2, \dots, B_{N-1}$ med lengde $N-1$. Siden styreleder K ikke kjenner informasjonen om høydene på bygningene, kan han ikke beregne verdiene av $A_i$.

Styreleder K tenkte at JOI må ha glemt å skrive ned ett tall. Ulike følger $A_1, A_2, \dots, A_N$ kan vurderes avhengig av høydene på bygningene. Blant disse, hvor mange følger finnes det slik at hvis man fjerner én verdi fra følgen, resulterer det i følgen $B_1, B_2, \dots, B_{N-1}$?

Merk at JOI i virkeligheten kan ha gjort andre feil da han skrev. Avhengig av verdiene til $B_1, B_2, \dots, B_{N-1}$ er det ikke sikkert at det finnes noen slik følge i det hele tatt.

Oppgave

Gitt en heltallsfølge $B_1, B_2, \dots, B_{N-1}$ med lengde $N-1$, skriv et program for å bestemme hvor mange følger $A_1, A_2, \dots, A_N$ som kan vurderes slik at fjerning av én verdi fra følgen resulterer i følgen $B_1, B_2, \dots, B_{N-1}$.

Inndata

Les følgende fra standard inndata:

• Den første linjen inneholder et heltall $N$. Dette representerer at det er $N$ bygninger langs hovedgaten fra flyplassen til overnattingsstedet.
• Den $j$-te linjen ($1 \le j \le N-1$) av de følgende $N-1$ linjene inneholder et heltall $B_j$. Dette er den $j$-te verdien i heltallsfølgen som er skrevet i notatet mottatt av styreleder K.

Utdata

Skriv ut heltallet som representerer antall følger $A_1, A_2, \dots, A_N$ slik at fjerning av én verdi fra følgen resulterer i følgen $B_1, B_2, \dots, B_{N-1}$ på en enkelt linje.

Begrensninger

Alle inndata oppfyller følgende betingelser:

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

Deloppgaver

1. (10 poeng) $N \le 8$ er oppfylt.
2. (30 poeng) $N \le 300$ er oppfylt.
3. (60 poeng) Ingen ytterligere begrensninger.

Eksempler

Inndata 1

4
1
1
2

Utdata 1

5

Det er 4 bygninger langs hovedgaten fra flyplassen til overnattingsstedet. La $H_i$ være høyden på bygning $i$. Ulike følger $A_1, A_2, A_3, A_4$ kan vurderes avhengig av høydene på bygningene. Blant disse er det 5 måter slik at fjerning av én verdi fra følgen resulterer i følgen $1, 1, 2$:

• Følgen $1, 2, 1, 2$. For eksempel, når $H_2 > H_4 > H_1 > H_3$, har vi $A_1 = 1, A_2 = 2, A_3 = 1, A_4 = 2$. Også når $H_2 > H_1 > H_4 > H_3$, har vi $A_1 = 1, A_2 = 2, A_3 = 1, A_4 = 2$.
• Følgen $1, 1, 2, 3$. For eksempel, når $H_4 > H_3 > H_1 > H_2$, har vi $A_1 = 1, A_2 = 1, A_3 = 2, A_4 = 3$.
• Følgen $1, 1, 2, 1$. For eksempel, når $H_3 > H_1 > H_2 > H_4$, har vi $A_1 = 1, A_2 = 1, A_3 = 2, A_4 = 1$.
• Følgen $1, 1, 2, 2$. For eksempel, når $H_3 > H_4 > H_1 > H_2$, har vi $A_1 = 1, A_2 = 1, A_3 = 2, A_4 = 2$.
• Følgen $1, 1, 1, 2$. For eksempel, når $H_4 > H_1 > H_2 > H_3$, har vi $A_1 = 1, A_2 = 1, A_3 = 1, A_4 = 2$.

Inndata 2

8
1
1
2
1
2
3
1

Utdata 2

15