## Alternative Solution of ABC385G

Without loss of generality, assume $K$ is non-negative.

$L(P)$ represent the number of different prefix max, and $R(P)$ represent the number of different suffix max. We aim to enumerate all possible pairs $(L(P), R(P))$ and solve them independently.

Assume $L(P) = K + c + 1, R(P) = c + 1$ for some integer $c$ satisfying $K + 2c + 1 \leq N$. This implies:

- $K + c$ elements update the prefix maximum on the left of $N$
- $c$ elements update the suffix maximum on the right of $N$

The number of ways to determine the relative order of these elements is given by $\binom{K + 2c}{c}$.

(For example, the red numbers in the following illustration show a possible ordering for $N = 7, K = 1, c = 1$)


To simplify the problem, we "reflect" the rectangles on the left of $N$ and order all the rectangles by their respective red numbers.


From this transformation, it becomes clear that
$$\begin{aligned}
&\#\{P : P \text{ is permutation of length N}, L(P) = K + c + 1, R(P) = c + 1\} = \\&\#\text\{Q : Q \text{ is permutation of length }N - 1, R(Q) = K + 2c\}
\end{aligned}$$

Thus, the problem reduces to counting $Q$, which can be achieved by considering permutations generated by inserting numbers from largest to smallest. This can be done using a dynamic programming approach:

- states: $dp\text{[number of element inserted][number of red element inserted]}$.
- base case: $dp[1][1] = 1$
- transition: $dp[i + 1][j] = i \cdot dp[i][j] + dp[i][j - 1]$
- final answer: $dp[n - 1][K + 2c]$

Notice that this DP recurrence is identical to the one for the Stirling numbers of the first kind. Specifically, $dp[n - 1][K + 2c]$ corresponds to ${n-1 \brack K + 2c}$.

So the final answer is $\sum\limits_{c = 0}^{\lfloor\frac{n - 1 - K}{2}\rfloor}\binom{K + 2c}{c}{n-1 \brack K + 2c}$, and the bottleneck of the computation lies in calculating the $(n-1)$-th row of the Stirling numbers of the first kind, which can be done in $O(n\lg^2 n)$ or $O(n\lg n)$.