This is an $$$O(n \log p)$$$ solution to 1312E - Array Shrinking. Here's the code 72870029.

Starting from the most basic case, consider the number of an array with the maximum value $$$v$$$ with location $$$k$$$:

Considering the left side of $$$k$$$, you need to ensure that it monotonically increases before $$$k$$$, so you can choose the number of $$$k-1$$$ from $$$v-1$$$ and arrange them in a row from small to large, which is $$$\tbinom{v-1}{k-1}$$$.

Then consider the right side of $$$k$$$, pick a number, which is the same as one of the vertical elements, and the number of schemes is $$$k-1$$$; next only need to select the number of $$$n-k-1$$$, which cannot be the same as any of the placed elements, so select $$$n-k-1$$$ from $$$v-1- (k-1)$$$, the number of schemes $$$\tbinom{v-1-(k-1)}{n-k-1}$$$. These $$$n-k$$$ numbers can be arranged in a row from large to small, which is $$$(k-1) \times \tbinom{v-1-(k-1)}{n-k-1}$$$.

According to the principle of multiplication, the number of such counts:

Note that the numerator is only related to $$$v$$$. The overall answer can be simplified:

After preprocessing the factorial,

Enumerate $$$v$$$ to calculate the numerator $$$\sum_{v = n-1} ^ {m} \prod_ {i = v-n + 2} ^ {v-1} i$$$;

Then enumerate $$$k$$$ and calculate the denominator $$$(k-2)! \times(n-k-1)!$$$.

Complexity $$$O (n \ log P)$$$, where $$$P = 998244353$$$.