Bubble Sort

Bubble Sort Is Just Bait

The first trap is thinking about bubble sort directly. Nope. The array length can be $10^6$, and we are counting permutations, so simulation is dead on arrival.

Take an element $a_i$. Let

$c_i =$ the number of earlier elements greater than $a_i$.

During one left-to-right bubble-sort round, this element can move left by at most one position, because after it swaps left once, the scan continues past it. So if there are $c_i$ larger elements before it, it needs at least $c_i$ rounds before all of them cross to its right.

Also, one such larger element crosses it each round until none remain. Therefore the number of bubble-sort rounds for the whole array is

$max_i c_i$.

For a prefix $p_1, p_2, ..., p_y$, define $c_y$ as the number of previous elements greater than $p_y$. Then

$b_y = max(c_1,c_2,...,c_y)$.

So the entire problem becomes counting valid inversion-code sequences $c$, not permutations directly.

Why We May Count Codes Instead Of Permutations

For 1-based positions, $0 <= c_i < i$. For 0-based positions, which the implementation uses, $0 <= c_i <= i$.

These sequences are in bijection with permutations. Given a permutation, the sequence is obvious. Given the sequence, reconstruct backwards: at position $i$, among the first $i+1$ elements, $p_i$ is the $(i+1-c_i)$-th smallest remaining value. Pick that from the sorted unused values and remove it. Unique sequence, unique permutation.

So now we count sequences $c_0, c_1, ..., c_{n-1}$ with $0 <= c_i <= i$.

Turning Range Constraints Into Point Constraints

For a fixed $k$, the values $b_y$ are nondecreasing, because each $b_y$ is a prefix maximum. Therefore the set of prefixes with $b_y <= k$ is an initial segment.

Let $x_k$ be the number of prefixes with $b_y <= k$.

The condition $l <= x_k <= r$ means:

• $x_k >= l$: the $l$-th prefix still satisfies $b_l <= k$.
• $x_k <= r$: if $r<n$, then the $(r+1)$-th prefix must already fail, so $b_{r+1}>k$.

In 0-based positions:

• At position $l-1$, the current maximum must be $<=k$.
• At position $r$, if $r<n$, the current maximum must be $>k$.

That is the big cleanup. Each restriction only affects at most two checkpoint positions.

Compression

We only care about:

• checkpoint positions: every $l-1$, every $r$ with $r<n$, and $n-1$;
• threshold values: every given $k$, plus $-1$ and $n-1$.

Sort and unique the thresholds:

$t_0=-1 < t_1 < ... < t_{s-1}=n-1$.

A DP state $j$ means the current prefix maximum $M$ lies in this bucket:

$t_{j-1} < M <= t_j$.

State $0$ is only a virtual starting state before we have processed anything.

For every checkpoint position, combine all requirements there:

• If some restriction says $M <= k$, then we need $j <= id(k)$.
• If some restriction says $M > k$, then we need $j > id(k)$.

So each checkpoint allows buckets

$lo < j <= hi$.

If that range is empty, the DP naturally becomes zero. No drama.

Counting One Gap

Suppose the previous checkpoint ended before position $L$, and the next checkpoint is $R$. We need to process all $c_i$ for $L <= i <= R$.

For a bound $K$, let $W(L,R,K)$ be the number of ways to choose the whole gap while keeping every $c_i <= K$.

At position $i$, without extra restrictions, $c_i$ has choices $0,1,...,i$. With $c_i <= K$, it has $min(i,K)+1$ choices. Therefore

$W(L,R,K) = product over i=L..R of (min(i,K)+1)$.

This can be computed in $O(log n)$ using factorials and powers:

• If $K<L$: all factors are $K+1$, so $W=(K+1)^{R-L+1}$.
• If $K>=R$: all natural limits apply, so $W=(R+1)! / L!$.
• Otherwise: factors grow until $K$, then become flat:

$W=(K+1)!/L! * (K+1)^{R-K}$.

Everything is modulo $998244353$.

DP Transition

Let $dp[j]$ be the number of ways before this gap with current maximum in bucket $j$.

To end in bucket $j$ after the gap, there are two cases.

First, we were already in bucket $j$. Then the old max already guarantees $M>t_{j-1}$, so the new gap only has to keep every value $<=t_j$. Contribution:

$dp[j] * W(L,R,t_j)$.

Second, we were in some lower bucket. Then the old max was $<=t_{j-1}$, so the gap must raise the maximum into bucket $j$: all new values must be $<=t_j$, but not all of them may be $<=t_{j-1}$. Contribution from all lower buckets:

$(dp[0]+...+dp[j-1]) * (W(L,R,t_j)-W(L,R,t_{j-1}))$.

Use prefix sums of $dp$ to get this in $O(1)$ per state.

After computing the transition for a checkpoint, delete states that violate that checkpoint's combined constraints.

Initialization And Answer

Start with $dp[0]=1$, the virtual empty maximum. After the first gap, only real buckets $1..s-1$ can be populated.

After processing the final checkpoint $n-1$, sum all real states.

The complexity is $O(qs log n)$, where $q <= 2m+1$ and $s <= m+2$, so effectively $O(m^2 log n)$ per test case. The statement guarantees the total $m^2$ is small enough, so this fits easily. Factorials up to $10^6$ are precomputed once.