일본에서 국제정보올림피아드가 개최됩니다. 전 세계에서 온 선수들을 환영하기 위해 공항에서 숙박 시설로 이어지는 대로변의 고층 빌딩들을 장식하기로 결정했습니다. 유명한 디자이너에게 디자인을 의뢰한 결과, 장식에 사용되는 빌딩들은 공항에서 숙박 시설 쪽으로 갈수록 높이가 점점 높아져야 한다고 합니다. 즉, 장식에 사용되는 빌딩들의 높이를 공항에서 가까운 순서대로 $h_1, h_2, h_3, \dots$라고 하면, 반드시 $h_1 < h_2 < h_3 < \dots$여야 합니다.
장식을 가능한 한 화려하게 만들기 위해, 가능한 한 많은 빌딩을 사용하고 싶습니다. 장식할 빌딩을 선정하는 업무를 맡은 JOI는 어떤 빌딩 소유주가 다음과 같은 무리한 요구를 해 올 가능성이 있다는 것을 깨달았습니다: "내 빌딩을 반드시 장식에 사용해 주십시오. 나아가 빌딩이 눈에 띄도록, 장식에 사용되는 모든 빌딩 중에서 내 빌딩이 숙박 시설에 가장 가까운 빌딩이 되도록 빌딩들을 선택해 주십시오."
공항에서 숙박 시설로 이어지는 대로변에는 $N$개의 빌딩이 있으며, 공항에서 $i$번째 빌딩($1 \le i \le N$)을 빌딩 $i$라고 부릅니다. $N$개의 빌딩의 높이는 모두 서로 다릅니다. JOI는 다음과 같은 값을 미리 계산해 두었습니다: "빌딩 $i$를 장식에 사용하고, 장식에 사용되는 모든 빌딩 중에서 빌딩 $i$가 숙박 시설에 가장 가까운 빌딩이 되도록 빌딩들을 선택할 때, 선택할 수 있는 빌딩의 최대 개수는 $A_i$이다."
JOI는 이렇게 계산한 정수열 $A_1, A_2, \dots, A_N$을 메모에 적어 일본정보올림피아드 위원회의 K 위원장에게 제출했습니다.
그러나 K 위원장이 받은 메모에는 실제로는 길이가 $N-1$인 정수열 $B_1, B_2, \dots, B_{N-1}$만 적혀 있었습니다. K 위원장은 빌딩들의 높이에 대한 정보를 알지 못하기 때문에 $A_i$의 값을 직접 계산할 수 없습니다.
K 위원장은 JOI가 숫자 하나를 적는 것을 깜빡했다고 생각했습니다. 빌딩들의 높이에 따라 다양한 수열 $A_1, A_2, \dots, A_N$을 생각할 수 있습니다. 이 중에서 수열의 값 하나를 지웠을 때 수열 $B_1, B_2, \dots, B_{N-1}$이 되는 수열은 몇 개나 있을까요?
단, 실제로는 JOI가 적는 과정에서 다른 실수를 했을 수도 있습니다. $B_1, B_2, \dots, B_{N-1}$의 값에 따라서는 그러한 수열이 하나도 존재하지 않을 수도 있습니다.
과제
길이가 $N-1$인 정수열 $B_1, B_2, \dots, B_{N-1}$이 주어졌을 때, 수열에서 값 하나를 지운 결과가 수열 $B_1, B_2, \dots, B_{N-1}$이 되는 가능한 수열 $A_1, A_2, \dots, A_N$의 개수를 구하는 프로그램을 작성하십시오.
입력
표준 입력에서 다음 데이터를 읽으십시오:
- 첫 번째 줄에는 정수 $N$이 주어집니다. 이는 공항에서 숙박 시설로 이어지는 대로변에 $N$개의 빌딩이 있음을 나타냅니다.
- 다음 $N-1$개의 줄 중 $j$번째 줄($1 \le j \le N-1$)에는 정수 $B_j$가 주어집니다. 이는 K 위원장이 받은 메모에 적힌 정수열의 $j$번째 값입니다.
출력
수열에서 값 하나를 지운 결과가 수열 $B_1, B_2, \dots, B_{N-1}$이 되는 수열 $A_1, A_2, \dots, A_N$의 개수를 나타내는 정수를 한 줄에 출력하십시오.
제한
모든 입력 데이터는 다음 조건을 만족합니다:
- $2 \le N \le 1\,000\,000$.
- $1 \le B_j \le N$ ($1 \le j \le N-1$).
서브태스크
- (10점) $N \le 8$을 만족합니다.
- (30점) $N \le 300$을 만족합니다.
- (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