题目描述

译自 JOISC 2015 Day2 T1「Building 3」。

给出一个长度为 $N - 1$ 的序列 $B_1, B_2, \dots, B_{N-1}$，求出有多少长度为 $N$ 序列 $A_1, A_2, \dots, A_N$ 满足：

• $A_1, A_2, \dots, A_N$ 删掉其中一个数后和 $B_1, B_2, \dots, B_{N-1}$ 一样；
• 存在一个长度为 $N$ 的排列 $H_1, H_2, \dots, H_N$，使得 $A_i$ 是以 $H_i$ 为结尾的最长递增子序列的长度。

输入格式

第一行包含一个整数 $N$，表示序列的长度。

接下来 $N - 1$ 行，第 $j$ ($1 \le j \le N - 1$) 行包含一个整数 $B_j$，含义如题所述。

输出格式

输出一个整数，表示满足条件的 $A_1, A_2, \dots, A_N$ 的个数。

4
1
1
2

5

总共有 $5$ 个满足条件的序列：

• $1, 2, 1, 2$：$H_2 > H_4 > H_1 > H_3$ 或者 $H_2 > H_1 > H_4 > H_3$。
• $1, 1, 2, 3$：$H_4 > H_3 > H_1 > H_2$。
• $1, 1, 2, 1$：$H_3 > H_1 > H_2 > H_4$。
• $1, 1, 2, 2$：$H_3 > H_4 > H_1 > H_2$。
• $1, 1, 1, 2$：$H_4 > H_1 > H_2 > H_3$。

8
1
1
2
1
2
3
1

15

数据范围与提示

对于全部数据，满足 $2 \le N \le 10^6, 1 \le B_j \le N$。

本题共有 $3$ 个子任务。每个子任务的分数和附加限制如下：