不知道大家是怎么做的，退役已久的老博士硬推了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(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;
}
```