题解：CF1699C The Third Problem

似乎没有题解写过这种做法。

首先对于排列，我们有一个性质：$\text{mex}_{i=1}^x p_i=\min_{i=x+1}^n p_i$。

考虑这个性质有什么用，发现它可以锁定所有前缀最小值 $pre_i$，后缀最小值 $suc_i$，即问题转化为：给定所有 $pre_i,suc_i$，求有多少个合法的排列。

显然我们一定可以锁定一些位置的值：如果 $pre_i \neq pre_{i-1}$，那么一定有 $p_i=pre_i$；如果 $suc_i \neq suc_{i+1}$，那么一定有 $p_i=suc_i$。

对于剩下的不能确定值的位置，它应该满足 $p_i>\max(pre_i,suc_i)$，考虑把所有这样的 $\max(pre_i,suc_i)$ 拎出来从大到小排序，乘法原理计算方案数即可。

时间复杂度 $\text{O}(n \log n)$，瓶颈在排序。