國際資訊奧林匹亞將在日本舉行。為了歡迎世界各地的選手，主辦方決定裝飾從機場通往住宿設施的大道沿線的高樓。委託一位著名設計師進行設計後，他表示，用於裝飾的樓房必須沿著從機場到住宿設施的方向越來越高。也就是說，若將用於裝飾的樓房依照距離機場由近到遠的順序，將其高度記為 $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