不知道大家是怎么做的，退役已久的老博士硬推了3小时。
首先分析一个排列$P$什么时候达到最少交换次数，按照下界的证明，每一次交换都应该使得$\delta(P):=\sum_{i=1}^n |i-p_i|$减少2，否则就并不能达到下界。
这样一来，我们可以观察到，如果$p_i\leq i$，那么这个数从始至终向右移动。类似地，如果$p_i\geq i$，这个数只能向左移动。所以如果$p_i\leq i$，那么$p_i$之前的数应该都比它小，否则会迫使$p_i$向左移动。同样，如果$p_i\geq i$，那么$p_i$之后的数都应该比他大。
这可以总结为，不存在三个指标$i<j<k$满足$p_i>p_j>p_k$，否则考虑$p_j$若$p_j\geq j$则它后面的数$p_k$比它大，若$p_j\leq j$则它前面的数$p_i$比它小，都将导致矛盾。反之如果排列中不存在三个下降的数，那么任意一次交换，必然都使得$\delta(P)$减少2，这是因为，如果我们交换了$p_i$和$p_{i+1}$，那么必有$p_i>p_{i+1}$,这时由于不存在三个下降的数，应有$p_i$前的数都比它小，$p_{i+1}$后的数都比它大。所以$i<p_i$且，$p_{i+1}<i+1$，这表明这次交换使得$\delta(P)$减少了2。从而每一次交换都会使$\delta(P)$减少2，故交换次数达到了下界。
这样一来，我们面对的将是一个纯粹的组合问题，问字典序大于某个排列的排列中，有多少排列不包含长度为3的下降子序列，下文中将称这个性质为"漂亮的“。字典序的处理比较常规，只需要枚举从哪一位开始第一次大于给定串就可以，这样我们就需要处理如下子问题: 固定前缀的排列中，有多少个是“漂亮的”？
首先应判断前缀中是否有长度$\geq 3$的下降子序列，如果有，方案数为0，还需判断一下，剩下数中的最小者是否能和前缀中的两个数组成下降子序列，这些都可以用简单的前缀数组解决，属于基本功。
接下来，如果上述情况未发生，注意到前缀对我们的影响将只剩下前缀中的最大数，因为我们已经判断前缀中取两数或三数，无法组成下降子序列。所以问题进一步简化为，在$m$个数的排列中，如果第一个数是$x$，有多少这样的排列不包含长度为3的下降子序列？这个问题递归性明显，我们尝试建立递推式。以下记上述子问题的方案数为$f(x,m)$。
当$x=m$时，$\{1,2,...,m-1\}$都在$m$后面，所以他们必然是有序的，这样只有$1$方案，故$f(m,m)=1$。
当$x=1,2$时，后面的$m-1$个数不可能和$x$形成长度为3的下降子序列，故后面$m-1$的排列方案为$\sum_{i=1}^{n-1} f(i,n-1)$种，即长度为$n-1$的不包含长度为$3$的下降子序列的排列总数。
当$3\leq x\leq n-1$时，考虑$x$后第一个大于x的数，设它的位置为$i\in \{2,...,x+1\}$，大小是$j\in \{x+1,...,m\}$。注意到$\{1,2,...,x-1\}$在$x$之后，故他们在排列中必然有序，这表明第$2$到第$i-1$个数必然是$1$到$i-2$，这也说明了为什么i的取值范围是$2$到$x+1$。这样一来，前$i$个数对后面的影响，可以简化为一个$j$，这样就把方案数转化到子问题$f(j-i+1,m-i+1)$上。所以我们得到递推式:
$
f(x,m)=\sum_{2\leq i\leq x+1\leq j \leq m}f(j-i+1,m-i+1)
$
，直接按照这个公式递推，复杂度较高，期望得分60分左右。
我们注意到$f$的相邻项之间存在大量重复，可将递推式简化为，
$
f(x,m)=f(x-1,m-1)+f(x+1,m)
$
按照这个公式递推，可以得到80分。
想要得到满分，我们还需要进一步求出$f$的通项。观察上式，我们容易联想到组合数的递推关系，
$
C(n,m)=C(n-1,m-1)+C(n-1,m)
$
于是我们试图将递推式往这个方向变形。令$g(x,m)=f(m-x,m)$，则我们可以得到$g(x,m)=g(x-1,m)+g(x,m-1)$, 其中边界条件为$g(0,i)=1$以及$g(j,i)=0,j\geq i$。至此，递推式已经完全拥有的组合数的组合解释，考虑一个$n\times m$的方格，要从点$(0,1)$走到点$(x,m)$，每次只能向右或向下行走，且不能碰到对角线(即横坐标永远小于纵坐标，对应上面的边界条件
$g(j,i)=0,j\geq i$)，问有几种方案。这个模型相当的经典，他就是我们的老朋友"卡塔兰数"，当然这里是广义的：有$x$个$-1$和$m$个$+ 1$，$m>x$,问有多少序列的任意前缀和都大于0。这可以用我们熟悉的翻转第一个碰到对角线的点的前缀的方法，或者构造满足边界条件的公式并使用数学归纳法证明，无论使用哪种方案，我们都可以得到
$
g(a,b)=C(a,a+b-1)-C(a-1,a+b-1)
$
验证一下·，带入$a=b-1=n$ (注意我们是从(0,1）出发)，我们就得到了常规的卡塔兰数的公式$C_n=C(n,2n)-C(n-1,2n)$。
在推出上述公式以后，代码方面难度极低，只需要处理好一些必备的前缀数组，会算组合数模$P$就行，这都在提高组的要求以内，想必对NOI选手是小菜一碟。
```cpp
#include <iostream>
#include <cstring>
using namespace std;
long long const N=1e6+3e5,P=998244353;
int n,t,p[N],r[N],sr[N],pr[N];
long long ans,fac[N],inv[N];
long long power(long long x, long long k){
k=(k+P-1) % (P-1);
long long ans=1;
for (long long i=1;i<=k;i*=2,x=(x*x) % P)
if (k & i) ans=(ans*x) % P;
return ans;
}
long long c(long long a, long long b){
if (a<0) return 0;
return fac[b]*inv[a] % P * inv[b-a] % P;
}
long long g(long long a, long long b){
return (c(a,a+b-1)-c(a-1,a+b-1)+P) % P;
}
int main(){
ios::sync_with_stdio(false);
fac[0]=inv[0]=1;
for (int i=1;i<N;i++){
fac[i]=fac[i-1]*i % P;
inv[i]=power(fac[i],P-2);
}
cin>>t;
while (t--){
cin>>n;
ans=0;
for (int i=1;i<=n;i++){
cin>>p[i];
r[i]=max(r[i-1],p[i]);
if (r[i-1]>p[i]) pr[i]=max(pr[i-1],p[i]); else pr[i]=pr[i-1];
}
sr[n]=p[n];
for (int i=n-1;i>=1;i--)
sr[i]=min(sr[i+1],p[i]);
for (int i=1;i<=n;i++){
if (r[i]<n) ans=(ans+g(n-r[i]-1,n-i+2)) % P;
if (pr[i-1]>p[i]) break;
if (i<n && p[i]<r[i-1] && (p[i]>sr[i+1])) break;
}
cout<<ans<<endl;
}
return 0;
}
```