P4769 [NOI2018] Bubble Sort.

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

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. ```plain 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$.

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 $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$.

### 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} | Test Point | $n_\mathrm{max} =$ | $\sum n \leq$ | Special Properties | |:-:|:-:|:-:|:-:| | $1$ | $8$ | $5 \ n_\mathrm{max}$ | None | | $2$ | $9$ | ^ | ^ | | $3$ | $10$ | ^ | ^ | | $4$ | $12$ | ^ | ^ | | $5$ | $13$ | ^ | ^ | | $6$ | $14$ | ^ | ^ | | $7$ | $16$ | ^ | ^ | | $8$ | $16$ | ^ | ^ | | $9$ | $17$ | ^ | ^ | | $10$ | $18$ | ^ | ^ | | $11$ | $18$ | ^ | ^ | | $12$ | $122$ | $700$ | $\forall i \enspace q_i = i$ | | $13$ | $144$ | ^ | None | | $14$ | $166$ | ^ | ^ | | $15$ | $200$ | ^ | ^ | | $16$ | $233$ | ^ | ^ | | $17$ | $777$ | $4000$ | $\forall i \enspace q_i = i$ | | $18$ | $888$ | ^ | None | | $19$ | $933$ | ^ | ^ | | $20$ | $1000$ | ^ | ^ | | $21$ | $266666$ | $2000000$ | $\forall i \enspace q_i = i$ | | $22$ | $333333$ | ^ | None | | $23$ | $444444$ | ^ | ^ | | $24$ | $555555$ | ^ | ^ | | $25$ | $600000$ | ^ | ^ | ### 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