Gossip: I guessed a conclusion when I was doing this problem. The number of longest ascending subsequences cannot exceed two. At that time, I felt it was false...

First of all, if a sequence can satisfy the lower bound, then each element in it must only move in the direction of its target. In addition, the movement of a number is determined by the number of numbers larger on the left and smaller on the right, and must be left first and then right. Therefore, for any number, there can be no numbers larger on the left and smaller on the right at the same time.

The above property, transformed again, is equivalent to the absence of descending subsequences with a length greater than or equal to three. Therefore, ah, the strange need in the title to meet the property of the lower bound of bubble sort is transformed into a more beautiful property by us.

Let's not consider that the dictionary order required by the topic is strictly greater than, that is, simply find the number of permutations. Obviously, we can directly \ (\ text{dp} \). Let's first consider the properties of a descending subsequence with a wave length greater than or equal to three. Let's assume that there is a descending subsequence with a length greater than or equal to three.

1. If the first number of this subsequence has been filled in by us, the rest of it cannot have a descending subsequence with a length greater than or equal to two.
2. If the first two numbers of the subsequence have been filled in by us, there can be no number smaller than the second number in the rest of the subsequence.

Therefore, we need to design a state to meet the two properties we listed. Let \ (f_{i,j} \) indicate the number of filled \ (I \), and the maximum number is \ (j \), and it is satisfied that there is no unfilled number, which is smaller than the last number of descending subsequence with the length of \ (2 \) of the filled number. Assuming that the number currently filled is \ (k \), there are two situations:

1. \(k < j \), then we will not update \ (j \), that is \ (f_{i+1,j}\leftarrow f_{i,j} \). However, at this time, it needs to be satisfied that the remaining number is not smaller than \ (K \), that is, \ (K \) is the smallest of the unfilled numbers.
2. \(k > j \), then we will update \ (j \), that is \ (f_{i+1,k}\leftarrow f_{i,j} \).

It can be found that the transfer of both is unique. However, we need to judge whether there are transfers in the above two cases. It can be proved that all cases can be transferred except the first case when \ (i=j \).

Note: this \ (\ text{dp} \) design method is very enlightening. Although it is generally done in \ (\ text{dp} \), it still needs some exercise to analyze the properties of the objects we need \ (\ text{dp} \) and add them to our state design.

This \ (\ text{dp} \) direct violence is \ (O(n^2) \), which is not very good, but it can be found by hand that this transfer is equivalent to the transfer of Cartland number, so we get the solution of \ (O(n) \).

Let's consider the dictionary order again at this time. In fact, the comparison of dictionary order only needs to compare the size of the next bit of \ (\ text{lcp} \), so we have an idea, that is, fill the same number as \ (Q \) in the first \ (i-1 \) bit, and fill the number greater than \ (q_i \) in \ (I \), so that we can get an arrangement greater than its dictionary order. It is easy to find that our operation is easily combined with the previous \ (\ text{dp} \) process.

Specifically, let's make \ (p_i=\max_{j=1}^{i}q_j \), so the arrangement of size relationship at the \ (I \) position actually contributes \ (1 \) at the position of \ (f_{i-1,p_{i}+1} \). Let's consider quickly calculating the contribution of \ (1 \) at this position to \ (f_{n,n} \), or using a method similar to Cartland number, We can subtract the scheme across the central axis from the total scheme, i.e. \ (\ binom {2n-i-p {I} {n-i + 1} - \ binom {2n-i-p {I} {n-i + 2} \).

Should be done? Remember to judge whether the prefix of this \ (q_i \) is legal. Here, you can use the linked list to judge whether the number inserted each time is the smallest, so the total complexity is \ (O(n) \).

#include<bits/stdc++.h>
using namespace std;
const int N=6e5+5;
const int MOD=998244353;
int ADD(int x,int y){return x+y>=MOD?x+y-MOD:x+y;}
int SUB(int x,int y){return x-y<0?x-y+MOD:x-y;}
int TIME(int x,int y){return (int)(1ll*x*y%MOD);}
int ksm(int x,int k=MOD-2){int res=1;for(;k;k>>=1,x=TIME(x,x))if(k&1)res=TIME(res,x);return res;}
int fact[N<<1],ifact[N<<1];
int C(int n,int m){
	if(n<0||m<0||n-m<0) return 0;
	return TIME(fact[n],TIME(ifact[m],ifact[n-m]));
}
int n,q[N],p[N],L[N],R[N],res;
void DEL(int x){
	R[L[x]]=R[x],L[R[x]]=L[x];
}
int solve(){
	cin>>n,R[0]=1,L[n+1]=n,res=0;
	for(int i=1;i<=n;++i) L[i]=i-1,R[i]=i+1;
	for(int i=1;i<=n;++i) scanf("%d",&q[i]);
	for(int i=1;i<=n;++i) p[i]=max(p[i-1],q[i]);
	for(int i=1;i<=n;++i){
		res=ADD(res,SUB(C(2*n-i-p[i],n-i+1),C(2*n-i-p[i],n-i+2)));
		if(q[i]<p[i]&&R[0]!=q[i]) break;else DEL(q[i]);
	}
	return printf("%d\n",res),0;
}
int main(){
	fact[0]=1;
	for(int i=1;i<(N<<1);++i) fact[i]=TIME(fact[i-1],i);
	ifact[(N<<1)-1]=ksm(fact[(N<<1)-1]);
	for(int i=(N<<1)-1;i>=1;--i) ifact[i-1]=TIME(ifact[i],i);
	int T;cin>>T;while(T--) solve();
	return 0;
}