國際資訊奧林匹克將會喺日本舉行。為咗歡迎世界各地嘅選手，主辦方決定裝飾由機場去住宿設施嗰條大路沿途嘅高樓。佢哋搵咗一位著名設計師負責設計，設計師話，用嚟裝飾嘅樓宇必須由機場往住宿設施嘅方向越嚟越高。即係話，如果將用嚟裝飾嘅樓宇由近機場到遠機場嘅高度依次記做 $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$ 嚟裝飾，而且喺揀咗嘅樓入面，樓宇 $i$ 必須最接近住宿設施，咁最多可以揀 $A_i$ 幢樓。」JOI 君將計出嚟嘅整數序列 $A_1,A_2,\ldots,A_N$ 寫喺紙條上，交畀資訊奧林匹克日本委員會嘅 K 理事長。
不過，K 理事長收到嘅紙條，其實只寫咗長度為 $N-1$ 嘅整數序列 $B_1,B_2,\ldots,B_{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}$ 嘅值，可能連一個符合條件嘅序列都冇。
任務
畀定一個長度為 $N-1$ 嘅整數序列 $B_1,B_2,\ldots,B_{N-1}$。請寫個程式，計出所有可能嘅整數序列 $A_1,A_2,\ldots,A_N$ 入面，有幾多種可以刪走一個位置嘅值之後，變成整數序列 $B_1,B_2,\ldots,B_{N-1}$。
輸入格式
由標準輸入讀入以下資料。
- 第一行有一個整數 $N$，代表由機場去住宿設施嗰條大路沿途有 $N$ 幢樓。
- 之後 $N-1$ 行入面，第 $j$ 行（$1 \le j \le N-1$）有一個整數 $B_j$。呢個係 K 理事長收到嘅紙條上嗰個整數序列嘅第 $j$ 個值。
輸出格式
喺標準輸出用一行輸出一個整數，表示所有可能嘅整數序列 $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$ 可以有好多種可能。其中刪走一個位置嘅值之後會變成整數序列 $1,1,2$ 嘅，有以下 $5$ 種。
- 整數序列 $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