การแข่งขันโอลิมปิกคอมพิวเตอร์ระหว่างประเทศจะจัดขึ้นที่ประเทศญี่ปุ่น เพื่อต้อนรับผู้เข้าแข่งขันจากทั่วโลก จึงมีแผนตกแต่งอาคารสูงตามถนนสายหลักจากสนามบินไปยังที่พัก เมื่อขอให้นักออกแบบชื่อดังออกแบบการตกแต่ง เขากล่าวว่าอาคารที่เลือกต้องมีความสูงเพิ่มขึ้นเรื่อย ๆ จากสนามบินไปยังที่พัก กล่าวคือ หากความสูงของอาคารที่เลือก เรียงจากใกล้สนามบินไปไกลเป็น $h_1,h_2,h_3,\ldots$ จะต้องมี $h_1<h_2<h_3<\cdots$.

เพื่อให้การตกแต่งสวยงามที่สุด จึงต้องการใช้อาคารให้มากที่สุด JOI 君 ซึ่งได้รับมอบหมายให้เลือกอาคาร นึกได้ว่าเจ้าของอาคารอาจยื่นคำขอที่เอาแต่ใจว่า “ต้องใช้อาคารของฉันในการตกแต่งด้วย และเพื่อให้อาคารของฉันเด่นที่สุด ต้องให้อาคารของฉันอยู่ใกล้ที่พักที่สุดในบรรดาอาคารที่เลือก”

มีอาคาร $N$ หลังตามถนนจากสนามบินไปยังที่พัก เรียกอาคารที่อยู่ใกล้สนามบินเป็นลำดับที่ $i$ ($1 \le i \le N$) ว่าอาคาร $i$ อาคารทั้ง $N$ หลังมีความสูงต่างกันทั้งหมด เพื่อเตรียมรับคำขอใด ๆ JOI 君 จึงคำนวณไว้ล่วงหน้าว่า “เมื่อเลือกอาคารโดยต้องใช้อาคาร $i$ และให้อาคาร $i$ อยู่ใกล้ที่พักที่สุดในบรรดาอาคารที่เลือก จำนวนอาคารที่เลือกได้มากที่สุดคือ $A_i$ หลัง” เขาจดลำดับจำนวนเต็ม $A_1,A_2,\ldots,A_N$ ที่คำนวณได้ แล้วส่งให้ประธาน K ของคณะกรรมการโอลิมปิกคอมพิวเตอร์ญี่ปุ่น

แต่กระดาษที่ประธาน K ได้รับกลับมีเพียงลำดับจำนวนเต็ม $B_1,B_2,\ldots,B_{N-1}$ ที่มีความยาว $N-1$ เท่านั้น ประธาน K ไม่ทราบความสูงของอาคาร จึงไม่สามารถคำนวณค่า $A_i$ ได้

ประธาน K คิดว่า JOI 君 คงลืมเขียนตัวเลขหนึ่งตัว ลำดับ $A_1,A_2,\ldots,A_N$ ที่เป็นไปได้มีหลายแบบขึ้นอยู่กับความสูงของอาคาร ในบรรดาลำดับเหล่านั้น มีกี่ลำดับที่เมื่อลบค่าหนึ่งตำแหน่งออกแล้วจะได้ $B_1,B_2,\ldots,B_{N-1}$?

อย่างไรก็ตาม JOI 君 อาจเขียนผิดอย่างอื่นด้วย ขึ้นอยู่กับค่า $B_1,B_2,\ldots,B_{N-1}$ อาจไม่มีลำดับที่เป็นไปได้เลยก็ได้

งานที่ต้องทำ

กำหนดลำดับจำนวนเต็ม $B_1,B_2,\ldots,B_{N-1}$ ที่มีความยาว $N-1$ ให้ จงเขียนโปรแกรมหาจำนวนลำดับ $A_1,A_2,\ldots,A_N$ ที่เป็นไปได้ ซึ่งเมื่อลบค่าหนึ่งตำแหน่งออกแล้วจะได้ลำดับ $B_1,B_2,\ldots,B_{N-1}$.

ข้อมูลนำเข้า

อ่านข้อมูลต่อไปนี้จากข้อมูลนำเข้ามาตรฐาน

• บรรทัดแรกมีจำนวนเต็ม $N$ แสดงว่ามีอาคาร $N$ หลังตามถนนจากสนามบินไปยังที่พัก
• บรรทัดที่ $j$ ($1 \le j \le N-1$) ของ $N-1$ บรรทัดถัดไปมีจำนวนเต็ม $B_j$ ซึ่งเป็นค่าลำดับที่ $j$ ของลำดับบนกระดาษที่ประธาน K ได้รับ

ข้อมูลส่งออก

แสดงจำนวนเต็มหนึ่งบรรทัดทางข้อมูลส่งออกมาตรฐาน เป็นจำนวนลำดับ $A_1,A_2,\ldots,A_N$ ที่เป็นไปได้ ซึ่งเมื่อลบค่าหนึ่งตำแหน่งออกแล้วจะได้ $B_1,B_2,\ldots,B_{N-1}$.

ข้อจำกัด

ข้อมูลนำเข้าทั้งหมดเป็นไปตามเงื่อนไขต่อไปนี้

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

งานย่อย

งานย่อย 1 [10 คะแนน]

• $N \le 8$.

งานย่อย 2 [30 คะแนน]

• $N \le 300$.

งานย่อย 3 [60 คะแนน]

ไม่มีข้อจำกัดเพิ่มเติม

ตัวอย่าง

ข้อมูลนำเข้า 1

4
1
1
2

ข้อมูลส่งออก 1

5

หมายเหตุ

มีอาคาร 4 หลังตามถนนจากสนามบินไปยังที่พัก ให้ความสูงของอาคาร $i$ เป็น $H_i$.

ลำดับ $A_1,A_2,A_3,A_4$ ที่เป็นไปได้มีหลายแบบขึ้นอยู่กับความสูงของอาคาร ในบรรดาลำดับเหล่านี้ มี 5 ลำดับต่อไปนี้ที่เมื่อลบค่าหนึ่งตำแหน่งแล้วได้ลำดับ $1,1,2$.

• ลำดับ $1,2,1,2$ ตัวอย่างเช่น เมื่อ $H_2>H_4>H_1>H_3$ จะได้ $A_1=1,A_2=2,A_3=1,A_4=2$ และเมื่อ $H_2>H_1>H_4>H_3$ ก็จะได้ $A_1=1,A_2=2,A_3=1,A_4=2$ เช่นกัน
• ลำดับ $1,1,2,3$ ตัวอย่างเช่น เมื่อ $H_4>H_3>H_1>H_2$ จะได้ $A_1=1,A_2=1,A_3=2,A_4=3$.
• ลำดับ $1,1,2,1$ ตัวอย่างเช่น เมื่อ $H_3>H_1>H_2>H_4$ จะได้ $A_1=1,A_2=1,A_3=2,A_4=1$.
• ลำดับ $1,1,2,2$ ตัวอย่างเช่น เมื่อ $H_3>H_4>H_1>H_2$ จะได้ $A_1=1,A_2=1,A_3=2,A_4=2$.
• ลำดับ $1,1,1,2$ ตัวอย่างเช่น เมื่อ $H_4>H_1>H_2>H_3$ จะได้ $A_1=1,A_2=1,A_3=1,A_4=2$.

ข้อมูลนำเข้า 2

8
1
1
2
1
2
3
1

ข้อมูลส่งออก 2

15