2998 「JOISC 2015 Day2」Building 3

译自 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 $ 的个数。

总共有 $ 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 $。

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

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