A Olimpíada Internacional de Informática será realizada no Japão. Para dar as boas-vindas aos competidores do mundo inteiro, decidiu-se decorar os prédios altos ao longo da avenida que liga o aeroporto ao alojamento. Ao encomendar o projeto a um designer famoso, ele disse que os prédios usados na decoração devem ficar cada vez mais altos no sentido do aeroporto para o alojamento. Ou seja, se as alturas dos prédios usados na decoração, em ordem de proximidade ao aeroporto, forem $h_1,h_2,h_3,\ldots$, deve valer $h_1<h_2<h_3<\cdots$.

Para tornar a decoração o mais vistosa possível, queremos usar o maior número possível de prédios. JOI-kun, encarregado de escolher os prédios, percebeu que algum proprietário poderia fazer uma exigência descabida: «Quero que meu prédio seja obrigatoriamente usado na decoração. Além disso, para que ele se destaque, quero que seja o prédio mais próximo do alojamento entre todos os usados na decoração».

Há $N$ prédios ao longo da avenida do aeroporto ao alojamento. Chamaremos de prédio $i$ o $i$-ésimo prédio mais próximo do aeroporto ($1\le i\le N$). As alturas dos $N$ prédios são todas distintas. Para estar preparado para qualquer exigência, JOI-kun calculou antecipadamente que, ao escolher prédios de modo que o prédio $i$ seja usado e seja o mais próximo do alojamento entre os escolhidos, o número máximo de prédios que podem ser escolhidos é $A_i$. JOI-kun anotou a sequência de inteiros $A_1,A_2,\ldots,A_N$ assim calculada e a entregou ao presidente K do Comitê Japonês da Olimpíada de Informática.

No entanto, a anotação recebida pelo presidente K continha apenas uma sequência de inteiros $B_1,B_2,\ldots,B_{N-1}$ de comprimento $N-1$. Como o presidente K não conhece as alturas dos prédios, não consegue calcular os valores de $A_i$.

O presidente K pensou que JOI-kun certamente havia esquecido de escrever um número. Dependendo das alturas dos prédios, há diversas sequências possíveis $A_1,A_2,\ldots,A_N$. Quantas delas se tornam a sequência $B_1,B_2,\ldots,B_{N-1}$ ao remover um valor em uma posição?

Porém, JOI-kun pode ter cometido outros erros ao escrever. Dependendo dos valores de $B_1,B_2,\ldots,B_{N-1}$, talvez não exista nenhuma sequência assim.

Tarefa

É dada uma sequência de inteiros $B_1,B_2,\ldots,B_{N-1}$ de comprimento $N-1$. Escreva um programa que determine quantas sequências possíveis $A_1,A_2,\ldots,A_N$ se tornam a sequência $B_1,B_2,\ldots,B_{N-1}$ ao remover um valor em uma posição.

Entrada

Leia os dados a seguir da entrada padrão.

• A primeira linha contém o inteiro $N$. Isso indica que há $N$ prédios ao longo da avenida do aeroporto ao alojamento.
• A $j$-ésima linha ($1\le j\le N-1$) das próximas $N-1$ linhas contém o inteiro $B_j$. Esse é o $j$-ésimo valor da sequência de inteiros escrita na anotação recebida pelo presidente K.

Saída

Escreva na saída padrão, em uma linha, um inteiro que represente a quantidade de sequências possíveis $A_1,A_2,\ldots,A_N$ que se tornam a sequência $B_1,B_2,\ldots,B_{N-1}$ ao remover um valor em uma posição.

Restrições

Todos os dados de entrada satisfazem as condições a seguir.

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

Subtarefas

Subtarefa 1 [10 pontos]

• $N\le 8$.

Subtarefa 2 [30 pontos]

• $N\le 300$.

Subtarefa 3 [60 pontos]

Não há restrições adicionais.

Exemplos

Entrada 1

4
1
1
2

Saída 1

5

Nota

Há 4 prédios ao longo da avenida do aeroporto ao alojamento. Seja $H_i$ a altura do prédio $i$.

Dependendo das alturas dos prédios, há diversas sequências possíveis $A_1,A_2,A_3,A_4$. Dentre elas, as cinco seguintes se tornam a sequência $1,1,2$ ao remover um valor em uma posição.

• A sequência $1,2,1,2$. Por exemplo, quando $H_2>H_4>H_1>H_3$, temos $A_1=1,A_2=2,A_3=1,A_4=2$. Além disso, quando $H_2>H_1>H_4>H_3$, também temos $A_1=1,A_2=2,A_3=1,A_4=2$.
• A sequência $1,1,2,3$. Por exemplo, quando $H_4>H_3>H_1>H_2$, temos $A_1=1,A_2=1,A_3=2,A_4=3$.
• A sequência $1,1,2,1$. Por exemplo, quando $H_3>H_1>H_2>H_4$, temos $A_1=1,A_2=1,A_3=2,A_4=1$.
• A sequência $1,1,2,2$. Por exemplo, quando $H_3>H_4>H_1>H_2$, temos $A_1=1,A_2=1,A_3=2,A_4=2$.
• A sequência $1,1,1,2$. Por exemplo, quando $H_4>H_1>H_2>H_3$, temos $A_1=1,A_2=1,A_3=1,A_4=2$.

Entrada 2

8
1
1
2
1
2
3
1

Saída 2

15