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