빌딩 3

국제정보올림피아드가 일본에서 열리게 되어, 세계 선수들을 환영하려고 공항에서 숙소까지 이어지는 대로변의 고층 빌딩을 장식하기로 했다. 유명한 디자이너는 장식에 쓰는 빌딩이 공항에서 숙소 쪽으로 갈수록 높아져야 한다고 말했다. 공항에 가까운 순서대로 장식 빌딩의 높이를 $h_1, h_2, h_3, \cdots$라 하면 $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 이사장이 받은 메모에는 길이 $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$의 값에 따라서는 이런 정수열이 하나도 없을 수도 있다.

길이 $N-1$의 정수열 $B_1, \ldots, B_{N-1}$이 주어진다. 가능한 정수열 $A_1, \ldots, A_N$ 중 한 위치의 값을 지웠을 때 $B_1, \ldots, B_{N-1}$이 되는 것의 개수를 구하라.

첫 줄에 대로변의 빌딩 수 $N$이 주어진다. 이어지는 $N-1$개의 줄 중 $j$번째 줄($1 \le j \le N-1$)에는 메모에 적힌 정수열의 $j$번째 값 $B_j$가 주어진다.

가능한 정수열 $A_1, \ldots, A_N$ 중 한 위치의 값을 지웠을 때 $B_1, \ldots, B_{N-1}$이 되는 것의 개수를 한 줄에 출력한다.

$2 \le N \le 1\,000\,000$

$1 \le B_j \le N$ ($1 \le j \le N-1$)