非常简洁优美的一道题。

考虑对于一个合法序列 ，找到一个唯一的排列 来对应它。

从大到小填排列 中的数，显然那些被一个区间覆盖且不是那个区间的 的位置是不能填的。我们在所有能填的位置中找到那个最靠左 的位置填入，然后将包含它的区间全都删掉，继续如下过程。

这样如果一个 序列是合法的，它会被唯一映射到一个结果排列 ，我们对能这样被生成出来的排列 计数即可。

先考察 的最大值位置 ，显然在填完 之后，左边和右边互不影响，而上述过程是尽量选择靠左的，所以我们会把左边的位置全部填完再来填右边的数。对于 右边的部分，因为左边对其没有限制，其是一个与原问题相似的子问题。对于 左边的部分，我们就要思考，为什么最大值恰好填在了 ，而不是填在 更左边的位置。当然是因为 左边没有可用的位置。考虑枚举 左边最大值位置 ，那么必须存在一个区间同时包含 和 ，否则 肯定比 要先填入，就矛盾了。

所以我们对左边的限制就是 要在一个区间 中。设 表示区间 ，最大值位置在 的方案数，转移是简单的。对 的限制也可以预处理。设 表示被 包含的右端点 的所有区间的最小左端点，容易 处理。

于是总时间复杂度 。做完了。