考虑一个新的排列 \(p\) 被得到，每次操作需要满足：
- 如果我们对 \([l,r]\) 的 \(mid\) 处断开，说明在当前局面下 \([l,mid]\) 与 \([mid+1,r]\) 的元素集合分别与目标排列 \(p\) 的对应区间元素集合相同。
为了避免重复计数，我们钦定如下操作方式：
- 只有无法直接找到一个 \(mid\) 分割时，才必须交换 Min Max。
- 在交换后，找最小的合法的 \(mid\) 进行分割。
不难发现经过如此限制后，对于一个目标排列，我们的操作方案唯一。
这里的操作方案唯一是指的一个策略唯一。
比如说最初 \([1,n]\) 的情况，我有唯一决策是否交换，然后唯一决策切割哪个位置，整体决策唯一。
然后递归到 \([1,mid],[mid+1,n]\) 两个子问题，其策略唯一。
那么就能够保证对于目标排列 \(p\) 这样的递归生成方式唯一。
考虑整个操作过程中的状态。
由于第一个方式的限制，模拟两三步操作，注意到我们只关心区间内最值下标位置，能够发现当前区间 \([l,r]\) 的最值下标位置只有三种情况：
-
\([l,r]\) 的元素集合与最初的 \(a[l,r]\) 完全一致。
最值下标位置也一致。
-
$ a[l,r]$ 中的最小值被交换出去，换入一个极大值（我们只需要知道这个值比 \(a[l,r]\) 所有数字都大即可）。
新最小值位置为原本的次小值位置，新最大值位置为原本的最小值位置。
-
\(a[l,r]\) 中的最大值被交换出去，换入一个极小值（我们只需要知道这个值比 \(a[l,r]\) 所有数字都小即可）。
新最小值位置为原本的最大值位置，新最大值位置为原本的次大值位置。
由于转移方式 \(2.\) 的限制，对于一个分割方案，需要枚举最小的可分割点，其前半段是不可分割的，后半段是任意的，因此需要设计不可分割和任意两个状态。
设计状态 \(f_{l,r,0/1/2},g_{l,r,0/1/2}\) 分别表示在区间状态为以上 \(0/1/2\) 之一时，\([l,r]\) 如果不执行交换找不到分割点 \(mid\) 的方案数，以及所有情况下的方案数。
考虑转移：
-
\(f_{l,r,0}\) 的转移：
不妨设 \(x,y\) 为原本的最小值，最大值下标。
这里不妨假设 \(x<y\)。
由于必须要进行交换才能够划分，所以划分点 $mid $ 必然在 \([x,y-1]\) 之间。
且划分后，左侧缺失最小值，变为状态 \(1\)，右侧变为状态 \(2\)。
可以有转移：
if(x<y)for(int i=x;i<y;++i)f[l][r][0]+=f[l][i][1]*g[i+1][r][2]%p;但是注意到，我们只保证了划分点在 \([x,y-1]\) 之间的方案，但如果本身存在划分点 \([y,r-1]\)，则会算重（本身不需要交换，但这个转移的确是合法的）。
所以需要容斥：
for(int i=max(x,y);i<r;++i)f[l][r][0]-=f[l][i][0]*g[i+1][r][0]%p;\(x>y\) 同理。
-
\(f_{l,r,1}\) 的转移：
沿用上面的变量定义。
此刻的最小值下标 \(nx\) 是原区间次小值下标，此刻的最大值下标是原区间最小值下标 \(x\)。
不妨同样设 \(nx<x\)。
首先划分点也是存在于 \([nx,x-1]\)，前半段交换后状态是 \(1\)，后半段交换后状态是 \(0\)。
同样需要容斥掉划分点在 \([x,r-1]\) 的情况，此刻前半段状态为 \(1\)，后半段状态同样为 \(0\)。
if(nx<x){for(int i=nx;i<x;++i)f[l][r][1]+=f[l][i][1]*g[i+1][r][0]%p;for(int i=x;i<r;++i)f[l][r][1]-=f[l][i][1]*g[i+1][r][0]%p; }\(nx>x\) 同理。
-
\(f_{l,r,2}\) 的转移。
类似于 \(f_{l,r,1}\)，可以自行推导。
-
\(g_{l,r,0/1/2}\) 的转移：
\(g\) 的方案数可以分为两类：
- 原本的 \(f\)——不存在划分点 \(mid\)。
- 一段 \(f\) 拼上一段 \(g\)：枚举划分点。
对于 \(0\) 这个状态，直接拼就好了，对于 \(1,2\) 的状态，分类讨论一下最值在哪一侧即可。
for(auto j:{0,1,2})f[l][r][j]=(f[l][r][j]%p+p)%p,g[l][r][j]=f[l][r][j]; for(int i=l;i<r;++i)g[l][r][0]+=f[l][i][0]*g[i+1][r][0]%p; for(int i=l;i<x;++i)g[l][r][1]+=f[l][i][0]*g[i+1][r][1]%p; for(int i=x;i<r;++i)g[l][r][1]+=f[l][i][1]*g[i+1][r][0]%p; for(int i=l;i<y;++i)g[l][r][2]+=f[l][i][0]*g[i+1][r][2]%p; for(int i=y;i<r;++i)g[l][r][2]+=f[l][i][2]*g[i+1][r][0]%p;
最终答案即为 \(g_{1,n,0}\)。