#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$ 满足：

1. $A_1, A_2, \dots, A_N$ 删掉其中一个数后和 $B_1, B_2, \dots, B_{N-1}$ 一样；
2. 存在一个长度为 $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$ 的个数。

---

样例 1

输入

4
1
1
2

输出

5

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

1. $1, 2, 1, 2$：$H_2 > H_4 > H_1 > H_3$ 或者 $H_2 > H_1 > H_4 > H_3$。
2. $1, 1, 2, 3$：$H_4 > H_3 > H_1 > H_2$。
3. $1, 1, 2, 1$：$H_3 > H_1 > H_2 > H_4$。
4. $1, 1, 2, 2$：$H_3 > H_4 > H_1 > H_2$。
5. $1, 1, 1, 2$：$H_4 > H_1 > H_2 > H_3$。

---

样例 2

输入

8
1
1
2
1
2
3
1

输出

15

---

数据范围与提示

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

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

Subtask	附加限制	分数
1	$N \le 8$	$10$
2	$N \le 300$	$30$
3	无附加限制	$60$