国际信息奥林匹克竞赛将在日本举行，为了欢迎来自世界各地的选手，主办方决定装饰从机场到住宿设施沿途的大楼。在咨询了一位著名设计师后，对方表示，用于装饰的大楼高度必须从机场向住宿设施方向逐渐增加。也就是说，如果将用于装饰的大楼高度按从机场到住宿设施的顺序记为 $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}$。请编写一个程序，计算有多少种可能的整数序列 $A_1, A_2, \dots, A_N$，使得从其中删去一个值后，得到的序列恰好为 $B_1, B_2, \dots, B_{N-1}$。
输入格式
从标准输入读取以下内容：
- 第 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}$。
数据范围
所有输入数据满足以下条件：
- $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