Kansainväliset tietojenkäsittelytieteen olympialaiset järjestetään Japanissa. Toivottaaksemme kilpailijat ympäri maailmaa tervetulleiksi on päätetty koristella pilvenpiirtäjät lentoasemalta majoitustiloihin johtavan pääkadun varrella. Kuuluisalta suunnittelijalta tilattiin suunnitelma, ja hän totesi, että koristeluun käytettävien rakennusten korkeuden täytyy kasvaa lentoasemalta majoitustiloja kohti mentäessä. Toisin sanoen, jos merkitsemme koristeluun käytettävien rakennusten korkeuksia järjestyksessä lentoasemaa lähimpänä olevasta alkaen $h_1, h_2, h_3, \dots$, niin on pädettävä $h_1 < h_2 < h_3 < \dots$.

Jotta koristeluista tulisi mahdollisimman näyttävät, haluamme käyttää mahdollisimman montaa rakennusta. Koristeltavien rakennusten valitsemisen tehtäväkseen saanut JOI tajusi, että jokin rakennuksen omistaja saattaa esittää kohtuuttoman pyynnön: "Haluan, että käytätte ehdottomasti minun rakennustani koristeluun. Lisäksi, jotta rakennus erottuisi joukosta, haluan teidän valitsevan rakennukset niin, että minun rakennukseni on lähimpänä majoitustiloja kaikista koristeluun käytetyistä rakennuksista."

Lentoasemalta majoitustiloihin johtavan pääkadun varrella on $N$ rakennusta, ja kutsumme lentoasemalta lukien $i$-ttä rakennusta ($1 \le i \le N$) rakennukseksi $i$. Kaikkien $N$ rakennuksen korkeudet ovat keskenään erilaisia. JOI on laskenut etukäteen seuraavan tiedon: "Kun rakennukset valitaan siten, että rakennusta $i$ käytetään koristeluun ja rakennus $i$ on lähimpänä majoitustiloja kaikista koristeluun käytetyistä rakennuksista, valittavissa olevien rakennusten enimmäismäärä on $A_i$."

JOI kirjoitti muistiin tällä tavoin lasketun kokonaislukujonon $A_1, A_2, \dots, A_N$ ja toimitti sen kansainvälisten tietojenkäsittelytieteen olympialaisten Japanin-komitean puheenjohtajalle K:lle.

Puheenjohtaja K:n saama muistiinpano sisälsi kuitenkin todellisuudessa vain pituutta $N-1$ olevan kokonaislukujonon $B_1, B_2, \dots, B_{N-1}$. Koska puheenjohtaja K ei tiedä rakennusten korkeuksia, hän ei voi laskea arvoja $A_i$.

Puheenjohtaja K ajatteli, että JOI on varmasti unohtanut kirjoittaa muistiin yhden luvun. Rakennusten korkeuksista riippuen voidaan harkita erilaisia jonoja $A_1, A_2, \dots, A_N$. Kuinka monta sellaista jonoa näiden joukossa on, että yhden arvon poistaminen jonosta tuottaa jonon $B_1, B_2, \dots, B_{N-1}$?

Huomaa, että todellisuudessa JOI on saattanut tehdä muitakin virheitä kirjoittaessaan. Arvoista $B_1, B_2, \dots, B_{N-1}$ riippuen tällaista jonoa ei välttämättä ole olemassa lainkaan.

Tehtävä

Kun on annettu pituutta $N-1$ oleva kokonaislukujono $B_1, B_2, \dots, B_{N-1}$, kirjoita ohjelma, joka selvittää, kuinka monta sellaista mahdollista jonoa $A_1, A_2, \dots, A_N$ on olemassa, että yhden arvon poistaminen jonosta tuottaa jonon $B_1, B_2, \dots, B_{N-1}$.

Syöte

Lue seuraavat tiedot vakiosyötteestä:

• Ensimmäinen rivi sisältää kokonaisluvun $N$. Tämä tarkoittaa, että lentoasemalta majoitustiloihin johtavan pääkadun varrella on $N$ rakennusta.
• Seuraavien $N-1$ rivin $j$-s rivi ($1 \le j \le N-1$) sisältää kokonaisluvun $B_j$. Tämä on puheenjohtaja K:n saamaan muistiinpanoon kirjoitetun kokonaislukujonon $j$-s arvo.

Tuloste

Tulosta yhdelle riville kokonaisluku, joka ilmaisee sellaisten jonojen $A_1, A_2, \dots, A_N$ lukumäärän, joista yhden arvon poistaminen tuottaa jonon $B_1, B_2, \dots, B_{N-1}$.

Rajoitukset

Kaikki syötetiedot toteuttavat seuraavat ehdot:

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

Osatehtävät

1. (10 pistettä) $N \le 8$ pätee.
2. (30 pistettä) $N \le 300$ pätee.
3. (60 pistettä) Ei lisärajoituksia.

Esimerkit

Syöte 1

4
1
1
2

Tuloste 1

5

Lentoasemalta majoitustiloihin johtavan pääkadun varrella on 4 rakennusta. Olkoon $H_i$ rakennuksen $i$ korkeus. Rakennusten korkeuksista riippuen voidaan harkita erilaisia jonoja $A_1, A_2, A_3, A_4$. Näiden joukossa on 5 tapaa, joissa yhden arvon poistaminen jonosta tuottaa jonon $1, 1, 2$:

• Jono $1, 2, 1, 2$. Esimerkiksi kun $H_2 > H_4 > H_1 > H_3$, saadaan $A_1 = 1, A_2 = 2, A_3 = 1, A_4 = 2$. Myös silloin, kun $H_2 > H_1 > H_4 > H_3$, saadaan $A_1 = 1, A_2 = 2, A_3 = 1, A_4 = 2$.
• Jono $1, 1, 2, 3$. Esimerkiksi kun $H_4 > H_3 > H_1 > H_2$, saadaan $A_1 = 1, A_2 = 1, A_3 = 2, A_4 = 3$.
• Jono $1, 1, 2, 1$. Esimerkiksi kun $H_3 > H_1 > H_2 > H_4$, saadaan $A_1 = 1, A_2 = 1, A_3 = 2, A_4 = 1$.
• Jono $1, 1, 2, 2$. Esimerkiksi kun $H_3 > H_4 > H_1 > H_2$, saadaan $A_1 = 1, A_2 = 1, A_3 = 2, A_4 = 2$.
• Jono $1, 1, 1, 2$. Esimerkiksi kun $H_4 > H_1 > H_2 > H_3$, saadaan $A_1 = 1, A_2 = 1, A_3 = 1, A_4 = 2$.

Syöte 2

8
1
1
2
1
2
3
1

Tuloste 2

15