Международная олимпиада по информатике будет проходить в Японии. Чтобы приветствовать участников со всего мира, решили украсить высотные здания вдоль главной улицы от аэропорта до места проживания. Когда за дизайном обратились к известному дизайнеру, он сказал, что высоты используемых для украшения зданий должны возрастать в направлении от аэропорта к месту проживания. Иными словами, если высоты выбранных зданий в порядке удаления от аэропорта равны $h_1,h_2,h_3,\ldots$, должно выполняться $h_1<h_2<h_3<\cdots$.

Чтобы украшение выглядело как можно торжественнее, хочется использовать как можно больше зданий. JOI, которому поручили выбрать здания, подумал, что владелец какого-нибудь здания может предъявить нелепое требование: «Обязательно используйте моё здание для украшения. Более того, чтобы оно выделялось, сделайте так, чтобы среди всех используемых зданий именно оно было ближе всего к месту проживания».

Вдоль главной улицы от аэропорта до места проживания расположено $N$ зданий. Назовём зданием $i$ здание, которое находится на $i$-м месте по близости к аэропорту ($1 \le i \le N$). Высоты всех $N$ зданий различны. Чтобы быть готовым к любому требованию, JOI заранее вычислил для каждого здания следующее: «Если выбрать здания так, чтобы использовать здание $i$ и чтобы среди всех выбранных зданий именно здание $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