题目分析

暂时不考虑必须严格大于给定排列的问题。
首先发现，如果序列中存在长度 $\geq 3$的下降序列的话，一定是不合法的。因为这样一个下降序列中间那个元素，会经过一次往左走的交换和一次往右走的交换，一定有一次离其目标位置远了，也就是走了一个无效步，不能达到下界。
这个条件可以转化为，原序列能被拆成两个上升序列。
进行 dp，考虑 $f(i,j)$表示还有 $i$个元素没放，其中 $j$个是比放了的元素更大的，这 $j$个元素我们称之为牛逼元素，然后将这些元素放完，有多少种方法。发现因为牛逼元素比较牛逼，所以随便放一个牛逼元素都是合法的，而如果放其他元素的话，只能放最小的那个，不然一定会出现第三个上升序列。
得到 dp 方程：$f(i,j)=\sum_{k=0}^j f(i-1,j-k)$
显然 $f(i,j)=f(i-1,j)+f(i,j-1)$
打表找规律，发现 $f(i,j)=C_{i+j-1}^j-C_{i+j-1}^{j-2}$，这个可以用数学归纳法证一波。于是在预处理阶乘和阶乘的逆元后，这东西就能 $O(1)$求了。
接下来开始考虑严格大于给定排列的限制。
设当前考虑到排列的第 $i$个元素的放法，并且前 $i-1$位放的元素和给定的排列里的元素一毛一样。设给出的排列这一位是 $a_i$，其后有 $b_i$个元素大于 $a_i$，有 $c_i$个元素小于 $a_i$。$b_i$和 $c_i$可以用树状数组求。
如果这一位放的元素大于 $a_i$，那么以后的位置不再受严格大于给定排列这个条件的限制，我们可以统一求一波。设当前这种情况下，还存在 $bg$个严格大于前 $i$个 $a$的元素，那么前 $i$位与 $a$相同后面不同的合法排列数就是：$\sum_{j=0}^{bg-1}f(n-i,j)=f(n-i+1,bg-1)$。当然啦，如果 $bg=0$，后面一定是从小到大放元素，一定是在取这种前缀条件下的最小排列，一定不是严格大于 $a$的排列，可以直接结束计算。
如果这一位放 $a_i$的话，检验一下 $a_i$是否是前面放法和 $a$相同条件下的牛逼元素或其他元素中最小的那个，不是就直接结束计算。
复杂度 $O(nlogn)$，瓶颈在树状数组。

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
const int N=600005,mod=998244353;
int T,n,ans,a[N],b[N],c[N],s[N],fac[N<<1],ni[N<<1];
int qm(int x) {return x>=mod?x-mod:x;}
int ksm(int x,int y) {
    int re=1;
    for(;y;y>>=1,x=1LL*x*x%mod) if(y&1) re=1LL*re*x%mod;
    return re;
}
int lowbit(int x) {return x&(-x);}
void add(int x) {while(x<=n) ++s[x],x+=lowbit(x);}
int query(int x) {int re=0;while(x) re+=s[x],x-=lowbit(x); return re;}
int C(int d,int u) {return 1LL*fac[d]*ni[u]%mod*ni[d-u]%mod;}
int getf(int i,int j) {
    if(j==0) return 1;
    if(j==1) return i;
    return qm(C(i+j-1,j)-C(i+j-1,j-2)+mod);
}
int main()
{
    T=read();
    fac[0]=1;for(RI i=1;i<=1200000;++i) fac[i]=1LL*fac[i-1]*i%mod;
    ni[1200000]=ksm(fac[1200000],mod-2);
    for(RI i=1199999;i>=0;--i) ni[i]=1LL*ni[i+1]*(i+1)%mod;
    while(T--) {
        n=read();
        for(RI i=1;i<=n;++i) a[i]=read(),s[i]=0;
        for(RI i=n;i>=1;--i)
            c[i]=query(a[i]),add(a[i]),b[i]=n-i-c[i];
        int flag,bg=n;ans=0;
        for(RI i=1;i<=n;++i) {
            if(b[i]<bg) bg=b[i],flag=1;
            else flag=0;
            if(!bg) break;
            ans=qm(ans+getf(n-i+1,bg-1));
            if(!flag&&b[i]<n-i) break;
        }
        printf("%d\n",ans);
    }
    return 0;
}