Міжнародна олімпіада з інформатики відбудеться в Японії. Щоб привітати учасників з усього світу, вирішили прикрасити висотні будівлі вздовж головної вулиці від аеропорту до місця проживання. Відомий дизайнер, якому доручили оформлення, сказав, що висоти вибраних будівель мають зростати в напрямку від аеропорту до місця проживання. Тобто, якщо позначити висоти вибраних будівель у порядку від найближчої до аеропорту через $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 будівлі. Позначимо висоту будівлі $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