Shohag Loves Inversions
Contest: CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 2200
Tags: combinatorics, dp, implementation, math

Shohag has an array $$$a$$$ of integers. Initially $$$a = [0, 1]$$$. He can repeatedly perform the following operation any number of times:

- Let $$$k$$$ be the number of inversions$$$^{\text{∗}}$$$ in the current array $$$a$$$.
- Insert $$$k$$$ at any position in $$$a$$$, including the beginning or the end.

For example, if $$$a = [4, 6, 2, 4]$$$, then the number of inversions is $$$k = 3$$$. So Shohag can obtain the following arrays after the operation: $$$[\textbf{3}, 4, 6, 2, 4]$$$, $$$[4, \textbf{3}, 6, 2, 4]$$$, $$$[4, 6, \textbf{3}, 2, 4]$$$, $$$[4, 6, 2, \textbf{3}, 4]$$$, and $$$[4, 6, 2, 4, \textbf{3}]$$$.

Given an integer $$$n$$$, help Shohag count, modulo $$$998\,244\,353$$$, the number of distinct arrays of length $$$n$$$ that can be obtained after performing the operations.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first and only line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 10^6$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output format:
For each test case, output an integer — the number of possible arrays modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the following $$$5$$$ arrays can be obtained (the inserted inversion count is shown in bold):

- $$$[0, 1] \rightarrow [0, \textbf{0}, 1] \rightarrow [0, 0, 1, \textbf{0}]$$$,
- $$$[0, 1] \rightarrow [0, \textbf{0}, 1] \rightarrow [0, 0, \textbf{0}, 1]$$$,
- $$$[0, 1] \rightarrow [0, 1, \textbf{0}] \rightarrow [0, 1, 0, \textbf{1}]$$$,
- $$$[0, 1] \rightarrow [0, 1, \textbf{0}] \rightarrow [0, 1, \textbf{1}, 0]$$$,
- $$$[0, 1] \rightarrow [0, 1, \textbf{0}] \rightarrow [\textbf{1}, 0, 1, 0]$$$.

Example input:
4
4
2
7
69

Example output:
5
1
682
325188814

Editorial:
It's hard to track the array when we insert new inversions as the inversion number can quickly become very large.
The key observation here is to notice what happens when the inversion count becomes more than $$$1$$$. As the initial array has only $$$0$$$ and $$$1$$$ as elements when we insert an inversion count that is more than $$$1$$$, the inversion count will be larger than any element of the array. And this gives us a way to control everything!
Let $$$\text{dp}_i$$$ be the number of final arrays of length $$$n$$$ we can get from the current array of length $$$i$$$ if the current number of inversions in it is larger than any element of the array.
Let $$$k$$$ be the number of inversions in the current array and $$$k > \max(a)$$$. Then
• If we insert $$$k$$$ not in the end, then the new inversion count will be more than $$$k$$$, so we get the same situation for $$$dp_{i+1}$$$
• Or if we insert $$$k$$$ in the end then the number of inversions will still be $$$k$$$. So if we inserted it $$$j$$$ times in the end and once somewhere else ($$$i$$$ ways to do so) then we will get the situation for $$$dp_{i+j+1}$$$
So $$$\text{dp}_i = (i \cdot \sum_{j > i} \text{dp}_j) + 1$$$, here $$$1$$$ is added as we can end the sequence here by inserting $$$k$$$ in the end $$$(n - i)$$$ times.
This can be computed with simple dp in $$$O(n)$$$ time using suffix sums.
Now we just need to deal with the starting array when it starts to have more than $$$1$$$ inversion.
There are $$$(n - 1)$$$ ways to finish the sequence having $$$\le 1$$$ inversion. And they are of the form $$$0, 0, \ldots, 0, [0, 1, 0], 1, \ldots, 1, 1$$$ this is because we first insert $$$0$$$ at the beginning for some time and then we get $$$1$$$ inversion count when we insert $$$0$$$ at the end for the first time and then we will have to insert $$$1$$$ at the end every time after that.
And to count the ways to get the starting array of length $$$m$$$ with more than $$$1$$$ inversion, we can notice that it's just the sum of ways where we insert $$$1$$$ before the first $$$1$$$ in any sequence of the form like above $$$0, 0, \ldots, 0, [0, 1, 0], 1, \ldots, 1, 1$$$. And if the position of the first $$$1$$$ is $$$j$$$ then we have $$$(j - 1)$$$ ways to do so. So total ways is $$$\sum_{j=2}^{m - 1} (j - 1) = \frac{(m - 2) \cdot (m - 1)}{2} - 1$$$
So the answer is just $$$n - 1 + \sum_{m=3}^{n} \left( \frac{(m - 2) \cdot (m - 1)}{2} - 1 \right) \cdot \text{dp}_m$$$
Time Complexity: $$$O(n)$$$
Note that there are ways to write the dp so that you don't have to handle the starting array separately. Also in this problem, we have limited the total sum of $$$n$$$ over all test cases. But there exists solutions where the solution works even without the limit but we decided to let both solutions pass.
Also, I am extremely sorry that during the contest we found out that some people found the second difference/derivative of the sequence on OEIS. We searched on OEIS before but couldn't find it, otherwise we would have modified the problem. Again, sorry for this issue.