题目描述

国际信息学奥林匹克竞赛将在日本举行，为了欢迎来自世界各地的选手，决定从机场到住宿设施沿途的高层建筑进行装饰。为此，委托了一位著名设计师进行设计。设计师表示，装饰所用的建筑高度必须从机场附近到住宿设施附近依次递增，即若将建筑高度记为 $h_1, h_2, h_3, \dots$，则必须满足 $h_1 < h_2 < h_3 < \cdots$。

为了尽可能多地装饰建筑，JOI 君被委任选择用于装饰的建筑。建筑所有者提出“我拥有的建筑必须被用于装饰”，同时还可能提出“我希望我拥有的建筑在所有被用于装饰的建筑中，离住宿设施最近”的无理要求。

从机场到住宿设施的大道沿途共有 $N$ 栋建筑，将离机场最近的第 $i$ 栋建筑记为建筑 $i$（$1 \le i \le N$）。所有建筑的高度各不相同。JOI 君为了应对各种可能的要求，预先计算了“若选择建筑 $i$ 用于装饰，且在所有被用于装饰的建筑中，建筑 $i$ 离住宿设施最近，则最多可选择的建筑数量为 $A_i$”这一信息，并将整数序列 $A_1, A_2, \dots, A_N$ 提交给信息学奥林匹克日本委员会的 K 理事长。

然而，K 理事长收到的备忘录上，实际上只写有长度为 $N-1$ 的整数序列 $B_1, B_2, \dots, B_{N-1}$，并未包含 $A_i$ 的完整信息。由于 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}$，求出有多少种可能的整数序列 $A_1, A_2, \dots, A_N$，使得从中删除一个元素后，得到的序列恰好是 $B_1, B_2, \dots, B_{N-1}$。

输入格式

从标准输入读入以下数据：

• 第一行包含一个整数 $N$，表示从机场到住宿设施沿途共有 $N$ 栋建筑。
• 接下来的 $N-1$ 行，第 $j$ 行（$1 \le j \le N-1$）包含一个整数 $B_j$，表示 K 理事长收到的备忘录中整数序列的第 $j$ 个值。

输出格式

在标准输出上输出一行，表示在所有可能的整数序列 $A_1, A_2, \dots, A_N$ 中，删除一个元素后能恰好得到整数序列 $B_1, B_2, \dots, B_{N-1}$ 的序列个数。

4
1
1
2

5

8
1
1
2
1
2
3
1

15

提示

样例 1 解释

从机场到住宿设施沿途共有 4 栋建筑。记建筑 $i$ 的高度为 $H_i$。

对于整数序列 $A_1, A_2, A_3, A_4$，由于建筑高度的不同，可能产生多种情况。其中，从该序列中删除一个元素后，得到整数序列 $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 \le N \le 1000000$
• $1 \le B_j \le N$（$1 \le j \le N-1$）

子任务

子任务 1 [10 分]

• $N \le 8$

子任务 2 [30 分]

• $N \le 300$

子任务 3 [60 分]

无额外限制。

翻译由 Qwen3-235B 完成