Alþjóðaólympíuleikarnir í upplýsingatækni eru haldnir í Japan. Til að bjóða keppendur hvaðanæva að úr heiminum velkomna hefur verið ákveðið að skreyta skýjakljúfana við aðalgötuna frá flugvellinum að gistiaðstöðunni. Frægur hönnuður var fenginn til að sjá um hönnunina og hann sagði að byggingarnar sem notaðar eru til skreytingar yrðu að hækka frá flugvellinum í átt að gistiaðstöðunni. Með öðrum orðum, ef við táknum hæðir bygginganna sem notaðar eru til skreytingar í röð frá þeirri sem er næst flugvellinum sem $h_1, h_2, h_3, \dots$, þá verður að gilda að $h_1 < h_2 < h_3 < \dots$.

Til að gera skreytingarnar sem glæsilegastar viljum við nota eins margar byggingar og mögulegt er. JOI, sem fékk það hlutverk að velja byggingarnar sem á að skreyta, áttaði sig á því að möguleiki væri á að eigandi byggingar kæmi með þá ósanngjörnu beiðni: „Ég vil að þið notið bygginguna mína hvað sem tautar og raular til skreytingar. Enn fremur, til að byggingin skeri sig úr, vil ég að þið veljið byggingarnar þannig að byggingin mín verði sú sem er næst gistiaðstöðunni af öllum þeim byggingum sem notaðar eru til skreytingar.“

Það eru $N$ byggingar við aðalgötuna frá flugvellinum að gistiaðstöðunni, og við köllum $i$-tu bygginguna frá flugvellinum ($1 \le i \le N$) byggingu $i$. Hæðir bygginganna $N$ eru allar ólíkar. JOI hefur reiknað út eftirfarandi fyrir fram: „Þegar byggingar eru valdar þannig að bygging $i$ sé notuð til skreytingar og bygging $i$ sé sú sem er næst gistiaðstöðunni af öllum byggingum sem notaðar eru til skreytingar, þá er hámarksfjöldi bygginga sem hægt er að velja $A_i$.“

JOI skrifaði niður heiltalnrununa $A_1, A_2, \dots, A_N$ sem reiknuð var á þennan hátt og skilaði henni til K formanns japönsku nefndarinnar fyrir Alþjóðaólympíuleikana í upplýsingatækni.

En miðinn sem K formaður fékk í hendurnar innihélt í raun aðeins heiltalnrunu $B_1, B_2, \dots, B_{N-1}$ af lengd $N-1$. Þar sem K formaður þekkir ekki upplýsingarnar um hæðir bygginganna getur hann ekki reiknað út gildin á $A_i$.

K formaður hélt að JOI hlyti að hafa gleymt að skrifa niður eina tölu. Ýmsar runur $A_1, A_2, \dots, A_N$ koma til greina eftir því hverjar hæðir bygginganna eru. Hversu margar slíkar runur eru þannig að ef eitt gildi er fjarlægt úr rununni þá fæst runan $B_1, B_2, \dots, B_{N-1}$?

Athugið að í raun og veru gæti JOI hafa gert önnur mistök við skriftirnar. Eftir því hver gildin á $B_1, B_2, \dots, B_{N-1}$ eru gæti verið að engin slík runa sé til.

Verkefni

Gefið heiltalnrunu $B_1, B_2, \dots, B_{N-1}$ af lengd $N-1$, skrifið forrit til að ákvarða hversu margar runur $A_1, A_2, \dots, A_N$ koma til greina þannig að ef eitt gildi er fjarlægt úr rununni þá fáist runan $B_1, B_2, \dots, B_{N-1}$.

Inntak

Lesið eftirfarandi úr staðalinntaki:

• Fyrsta línan inniheldur heiltölu $N$. Þetta táknar að það eru $N$ byggingar við aðalgötuna frá flugvellinum að gistiaðstöðunni.
• $j$-ta línan ($1 \le j \le N-1$) af næstu $N-1$ línum inniheldur heiltölu $B_j$. Þetta er $j$-ta gildið í heiltalnrununni sem skrifuð var á miðann sem K formaður fékk.

Úttak

Prentið á einni línu heiltöluna sem táknar fjölda runa $A_1, A_2, \dots, A_N$ þannig að ef eitt gildi er fjarlægt úr rununni þá fáist runan $B_1, B_2, \dots, B_{N-1}$.

Skorður

Öll inntaksgögn uppfylla eftirfarandi skilyrði:

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

Undirverkefni

1. (10 stig) $N \le 8$ er uppfyllt.
2. (30 stig) $N \le 300$ er uppfyllt.
3. (60 stig) Engar frekari skorður.

Dæmi

Inntak 1

4
1
1
2

Úttak 1

5

Það eru 4 byggingar við aðalgötuna frá flugvellinum að gistiaðstöðunni. Látum $H_i$ vera hæð byggingar $i$. Ýmsar runur $A_1, A_2, A_3, A_4$ koma til greina eftir því hverjar hæðir bygginganna eru. Meðal þeirra eru 5 möguleikar þannig að ef eitt gildi er fjarlægt úr rununni þá fæst runan $1, 1, 2$:

• Runan $1, 2, 1, 2$. Til dæmis, þegar $H_2 > H_4 > H_1 > H_3$, þá höfum við $A_1 = 1, A_2 = 2, A_3 = 1, A_4 = 2$. Einnig, þegar $H_2 > H_1 > H_4 > H_3$, þá höfum við $A_1 = 1, A_2 = 2, A_3 = 1, A_4 = 2$.
• Runan $1, 1, 2, 3$. Til dæmis, þegar $H_4 > H_3 > H_1 > H_2$, þá höfum við $A_1 = 1, A_2 = 1, A_3 = 2, A_4 = 3$.
• Runan $1, 1, 2, 1$. Til dæmis, þegar $H_3 > H_1 > H_2 > H_4$, þá höfum við $A_1 = 1, A_2 = 1, A_3 = 2, A_4 = 1$.
• Runan $1, 1, 2, 2$. Til dæmis, þegar $H_3 > H_4 > H_1 > H_2$, þá höfum við $A_1 = 1, A_2 = 1, A_3 = 2, A_4 = 2$.
• Runan $1, 1, 1, 2$. Til dæmis, þegar $H_4 > H_1 > H_2 > H_3$, þá höfum við $A_1 = 1, A_2 = 1, A_3 = 1, A_4 = 2$.

Inntak 2

8
1
1
2
1
2
3
1

Úttak 2

15