האולימפיאדה הבינלאומית במדעי המחשב תיערך ביפן, ולכבוד קבלת פני המתחרים מכל העולם הוחלט לקשט את הבניינים הגבוהים לאורך השדרה שמנמל התעופה למקום הלינה. כאשר פנו למעצב מפורסם, הוא אמר שהבניינים הנבחרים לקישוט חייבים להיות גבוהים יותר ויותר בכיוון מנמל התעופה למקום הלינה. כלומר, אם גובהי הבניינים הנבחרים לפי סדר קרבתם לנמל התעופה הם $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$ הופכות לסדרה הנתונה כאשר מסירים מהן ערך במקום אחד.

קלט

קראו את הנתונים הבאים מהקלט הסטנדרטי.

• השורה הראשונה מכילה מספר שלם $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$. מביניהן, חמש הסדרות הבאות הופכות לסדרה $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