Background

Please note that the testdata includes cases with $n = 0$.

Problem Description

Recently, Xiao S has become very interested in bubble sort. To simplify the problem, Xiao S only studies bubble sorting permutations of $1$ to $n$.

Below is the algorithm description of bubble sort.

Input: a permutation p[1...n] of length n
Output: the sorted result of p.
for i = 1 to n do
	for j = 1 to n - 1 do
		if(p[j] > p[j + 1])
			swap the values of p[j] and p[j + 1]

The number of swaps in bubble sort is defined as the number of times the swap operation is executed. It can be proven that a lower bound of the swap count is $\frac 1 2 \sum_{i=1}^n \lvert i - p_i \rvert$, where $p_i$ is the number at position $i$ in the permutation $p$. If you are interested in the proof, you can read the hint.

Xiao S starts focusing on permutations of length $n$ that satisfy swap count $= \frac 1 2 \sum_{i=1}^n \lvert i - p_i \rvert$ (later, for convenience, we call all such permutations “good” permutations). He further wonders: are there many such permutations? Are they dense?

For a given permutation $q$ of length $n$, Xiao S wants to compute the number of “good” permutations that are strictly greater than $q$ in lexicographical order. However, he cannot do it, so he asks you for help. Since the answer may be very large, you only need to output the result modulo $998244353$.

Input Format

The first line contains a positive integer $T$, indicating the number of test cases.

For each test case, the first line contains a positive integer $n$, with $n \leq 6 \times 10^5$.

The next line contains $n$ positive integers, corresponding to $q_i$ in the statement, and it is guaranteed that the input is a permutation of $1$ to $n$.

Output Format

Output $T$ lines, each containing one integer.

For each test case, output one integer: the number of “good” permutations that are strictly greater than $q$ in lexicographical order, modulo $998244353$.

1
3
1 3 2

3

1
4
1 4 2 3

9

Hint

More Samples

Please download more samples from the attachment.

Sample 3

See inverse3.in and inverse3.ans in the attachment.

Explanation for Sample 1

Among the permutations that are lexicographically greater than $1 \ 3 \ 2$, all of them are “good” except $3 \ 2 \ 1$, so the answer is $3$.

Constraints

Below is a description of the input size for each test point.

For all testdata, it holds that $T = 5$ (samples may not satisfy this).

Let $n_\mathrm{max}$ be the maximum $n$ among the test cases, and let $\sum n$ be the sum of $n$ over all test cases.

::cute-table{tuack}

Hint

Below is the proof that a lower bound of the swap count is $\frac 1 2 \sum_{i=1}^n \lvert i - p_i \rvert$.

Sorting is essentially moving numbers, so the number of swaps in sorting can be described by the total distance that numbers move. For position $i$, suppose the number at this position in the initial permutation is $p_i$. Then we need to move this number to position $p_i$, and the moving distance is $\lvert i - p_i \rvert$. Therefore, the total moving distance is $\sum_{i=1}^n \lvert i - p_i \rvert$. Each step of bubble sort swaps two adjacent numbers, and each swap can reduce the total moving distance by at most $2$. Hence, $\frac 1 2 \sum_{i=1}^n \lvert i - p_i \rvert$ is a lower bound of the swap count in bubble sort.

Not all permutations reach this lower bound. For example, when $n = 3$, consider the permutation $3 \ 2 \ 1$. The number of swaps after bubble sorting this permutation is $3$, but $\frac 1 2 \sum_{i=1}^n \lvert i - p_i \rvert$ is only $2$.

Translated by ChatGPT 5