只需要对于每个 $n$，求出以下条件的长度为 $n$ 的排列个数 $f_n$（假设 $f_0=1$）：

右端点为 $p_i$（$i< n$） 的最长值域连续段的左端点为 $p_i$。

设长度为 $n$（$n\ge 1$）的排列个数的 OGF 为 $G=\sum_{i\ge 1}i!x^i$，则 $G=x^2G^{\prime}+Gx+x$

那么，设 $F\left(x\right)$ 为 $f$ 的 OGF，则

$$ F\left(G\right)=\dfrac{G}{x} $$

因为对于任意一个排列，从右往左贪心即可得到唯一一种划分方式。

$$ \begin{aligned} F^{\prime}\left(G\right)&=\dfrac{\left(G/x\right)^{\prime}}{G^{\prime}}\\ &=\dfrac{1}{x}-\dfrac{G}{G^{\prime}x^2}\\ &=\dfrac{F\left(G\right)}{G}-\dfrac{G}{G-\dfrac{G^2}{F\left(G\right)}-\dfrac{G}{F\left(G\right)}}\\ &=\dfrac{F\left(G\right)}{G}-\dfrac{F\left(G\right)}{F\left(G\right)-G-1}\\ F^{\prime}&=\dfrac{F}{x}-\dfrac{F}{F-x-1} \end{aligned} $$

移项可得，$\forall n\ge 1,f_n=\left(3-n\right)f_{n-1}+\sum_{1\le i<n}\left(i-1\right)f_if_{n-i}$

分治 NTT 即可。