Międzynarodowa Olimpiada Informatyczna odbędzie się w Japonii. Aby powitać zawodników z całego świata, postanowiono udekorować wieżowce stojące wzdłuż głównej ulicy prowadzącej z lotniska do miejsca zakwaterowania. Poproszony o projekt znany projektant stwierdził, że budynki wykorzystane do dekoracji muszą być coraz wyższe w kierunku od lotniska do miejsca zakwaterowania. Innymi słowy, jeśli wysokości wybranych budynków, w kolejności od najbliższego lotniska, oznaczymy przez $h_1,h_2,h_3,\ldots$, musi zachodzić $h_1<h_2<h_3<\cdots$.

Aby dekoracja była jak najbardziej okazała, chcemy wykorzystać jak najwięcej budynków. JOI, któremu powierzono ich wybór, pomyślał, że właściciel któregoś budynku może wystąpić z nierozsądnym żądaniem: „Mój budynek koniecznie musi zostać wykorzystany do dekoracji. Co więcej, aby się wyróżniał, spośród wszystkich dekorowanych budynków musi być położony najbliżej miejsca zakwaterowania”.

Wzdłuż głównej ulicy prowadzącej z lotniska do miejsca zakwaterowania stoi $N$ budynków. Budynek $i$ ($1 \le i \le N$) oznacza $i$-ty budynek, licząc od lotniska. Wszystkie $N$ budynków ma różne wysokości. Aby być przygotowanym na każde takie żądanie, JOI obliczył wcześniej, że „jeśli wybieramy budynki tak, aby budynek $i$ został udekorowany i był najbliższy miejscu zakwaterowania spośród wybranych budynków, maksymalna liczba wybranych budynków wynosi $A_i$”. JOI zapisał tak obliczony ciąg liczb całkowitych $A_1,A_2,\ldots,A_N$ i przekazał notatkę przewodniczącemu K Japońskiego Komitetu Olimpiady Informatycznej.

Jednak na notatce otrzymanej przez przewodniczącego K znajdował się jedynie ciąg $B_1,B_2,\ldots,B_{N-1}$ długości $N-1$. Przewodniczący K nie zna wysokości budynków, więc nie może obliczyć wartości $A_i$.

Przewodniczący K uznał, że JOI musiał zapomnieć zapisać jedną liczbę. W zależności od wysokości budynków możliwe są różne ciągi $A_1,A_2,\ldots,A_N$. Ile spośród nich po usunięciu jednej wartości daje ciąg $B_1,B_2,\ldots,B_{N-1}$?

JOI mógł jednak popełnić również inne błędy przy zapisywaniu. W zależności od wartości $B_1,B_2,\ldots,B_{N-1}$ może się zdarzyć, że nie istnieje żaden taki ciąg.

Zadanie

Dany jest ciąg liczb całkowitych $B_1,B_2,\ldots,B_{N-1}$ długości $N-1$. Napisz program obliczający liczbę możliwych ciągów $A_1,A_2,\ldots,A_N$, z których po usunięciu jednej wartości otrzymuje się ciąg $B_1,B_2,\ldots,B_{N-1}$.

Wejście

Wczytaj następujące dane ze standardowego wejścia.

• W pierwszym wierszu znajduje się liczba całkowita $N$. Oznacza ona, że wzdłuż głównej ulicy z lotniska do miejsca zakwaterowania stoi $N$ budynków.
• W $j$-tym ($1 \le j \le N-1$) z kolejnych $N-1$ wierszy znajduje się liczba całkowita $B_j$. Jest to $j$-ta wartość ciągu zapisanego na notatce otrzymanej przez przewodniczącego K.

Wyjście

Wypisz w jednym wierszu standardowego wyjścia liczbę całkowitą oznaczającą liczbę możliwych ciągów $A_1,A_2,\ldots,A_N$, z których po usunięciu jednej wartości otrzymuje się ciąg $B_1,B_2,\ldots,B_{N-1}$.

Ograniczenia

Wszystkie dane wejściowe spełniają poniższe warunki.

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

Podzadania

Podzadanie 1 [10 punktów]

• Zachodzi $N \le 8$.

Podzadanie 2 [30 punktów]

• Zachodzi $N \le 300$.

Podzadanie 3 [60 punktów]

Brak dodatkowych ograniczeń.

Przykład

Wejście 1

4
1
1
2

Wyjście 1

5

Uwagi

Wzdłuż głównej ulicy z lotniska do miejsca zakwaterowania stoją $4$ budynki. Niech $H_i$ oznacza wysokość budynku $i$.

W zależności od wysokości budynków możliwe są różne ciągi $A_1,A_2,A_3,A_4$. Spośród nich następujących pięć daje ciąg $1,1,2$ po usunięciu jednej wartości.

• Ciąg $1,2,1,2$. Na przykład, gdy $H_2>H_4>H_1>H_3$, otrzymujemy $A_1=1,A_2=2,A_3=1,A_4=2$. Również gdy $H_2>H_1>H_4>H_3$, otrzymujemy $A_1=1,A_2=2,A_3=1,A_4=2$.
• Ciąg $1,1,2,3$. Na przykład, gdy $H_4>H_3>H_1>H_2$, otrzymujemy $A_1=1,A_2=1,A_3=2,A_4=3$.
• Ciąg $1,1,2,1$. Na przykład, gdy $H_3>H_1>H_2>H_4$, otrzymujemy $A_1=1,A_2=1,A_3=2,A_4=1$.
• Ciąg $1,1,2,2$. Na przykład, gdy $H_3>H_4>H_1>H_2$, otrzymujemy $A_1=1,A_2=1,A_3=2,A_4=2$.
• Ciąg $1,1,1,2$. Na przykład, gdy $H_4>H_1>H_2>H_3$, otrzymujemy $A_1=1,A_2=1,A_3=1,A_4=2$.

Wejście 2

8
1
1
2
1
2
3
1

Wyjście 2

15