تقرر إقامة الأولمبياد الدولي للمعلوماتية في اليابان، وللترحيب بالمتسابقين من أنحاء العالم، تقرر تزيين المباني الشاهقة الواقعة على طول الشارع الرئيسي بين المطار ومكان الإقامة. وعندما طُلب من مصمم مشهور وضع التصميم، قال إن ارتفاعات المباني المستخدمة في الزينة يجب أن تتزايد عند الاتجاه من المطار إلى مكان الإقامة. أي إذا رمزنا إلى ارتفاعات المباني المستخدمة في الزينة، بترتيب قربها من المطار، بالرموز $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$ في الزينة، ويكون هو الأقرب إلى مكان الإقامة من بين المباني المستخدمة، فإن أكبر عدد ممكن من المباني المختارة هو $A_i$». كتب JOI المتتالية الصحيحة $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 مبانٍ على طول الشارع الرئيسي بين المطار ومكان الإقامة. ليكن $H_i$ ارتفاع المبنى $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