签到题我都不会做，我爬了。

首先检测一些明显非法的情况:

1. $h_i\geq n$，明显不可能，$h_i$上限是$n-1$

2. $h_i<h_{i-1}$(对于$i\geq 2$)，最大值不会减小，最小值不会增大，所以$h_i$一定是单调不减的。

3. $h_1\neq 0$，这很显然。

4. $h_n\neq n-1$这也很显然。

然后我们考虑从第$2$个元素开始枚举，我们维护一个gap变量，用以存储"在当前这个位置，一共有多少个位置可以填数，并且保证填了数之后不影响当前位置前缀最大值和前缀最小值的取值"。当前枚举到第$i$个元素时：

• 如果$h_i=h_{i-1}$，那就说明当前这个位置的值没有改变前缀最值的分布，那么总答案就可以乘上gap（因为有这么多的方案数让我们来填，并且填了后不影响前缀最值），并且 gap要减掉1，因为我们填了个数后占了一个空位。
• 如果$h_i>h_{i-1}$，那就说明当前这个位置的值改变了前缀最大值或者前缀最小值二者之一，那么总答案乘上2。同时gap要加上$h_i-h_{i-1}-1$，因为我们新创造了这么多的空位。