正解

首先在分析问题的时候不难发现操作的一个性质就是同一个 $x_i$ 对应多个所谓的 $p_{[l,r]}$ 序列。

对于这种操作对应多个序列不好计数的限制，一般情况下我们有下面两种思路

探究一下什么序列能够被得到，而不是从操作序列的角度设计 DP 状态。
若硬是从操作序列入手，我们可以通过给操作附上某种特定的顺序，让每一个序列都附上一个唯一的代表元，而这个代表元就是我们需要分题目去设计的。

如果你从第一个思路想的话你会很快陷入瓶颈，不建议自行尝试不然你会很痛苦。

我们从第二个思路入手，那么我们要对操作序列确定一个顺序，使得我们的决策可以唯一化。

考虑用插入法，我们可以从大到小钦定每一个值的位置，就是倒着遍历 $n,n-1,n-2,\dots,2,1$ ,。每一次我们把对应的值插到当前最左端的位置。

通过这种方式，我们可以将问题从对 $x$ 计数变为对上面合法构造的排列 $p$ 进行计数。

考虑如果 DP，注意到每一次操作都是涉及的是 $\max$ 操作，不妨考虑利用大根堆笛卡尔树的形态进行刻画，笛卡尔树一个很好的特性就是形态是确定的而不是变化的。

那么原题目中的最大值位置 $x_i$ 能够产生贡献的区间一定是一个排列上的连续区间，对应到笛卡尔树上就是笛卡尔树的一个子树。那么现在问题转化为对笛卡尔树形态计数，考虑枚举最大值 DP，设 $f(l,r,k)$ 表示当前枚举的最大值位置在大于等于 $k$ 的范围，管辖的子树区间为 $[l,r]$ 的笛卡尔树形态数量。

转移显然可以考虑递归处理 $[l,k-1],[k+1,r]$ ，或者从 $f[l,r,k+1]$ 传递过来，对于 $f(k+1,r,*)$ 的这个第三维是好说的，就是 $k+1$ 。但是 $f(l,k-1,*)$ 是比较难以确定的，因为我们不好确定这个范围。

这里有一个结论，设 $k'$ 表示 $[l,k-1]$ 最大值的位置，那么 $[l,r]$ 合法的充要条件是： $[l,k-1],[k+1,r]$ 是合法的，并且不能存在一个 $l\le l_i \le k' \le k \le r_i \le r$ 。

必要性是显然的，假设不存在 $l\le l_i \le k' \le k \le r_i \le r$ 的话那么我直接把最大值钦定为 $k'$ 也是合法的。考虑证明充分性，如果存在 $l\le l_i \le k' \le k \le r_i \le r$ ，那么根据前提条件左区间合法性可以知道把最大值钦定在 $k'$ 的左边都是不合法的，而如果把最大值钦定在 $[k',k)$ 中某个位置，那么 $x_i \neq k$ 了，所以最左端和发位置就是 $k$ 了，证毕。