首先考虑排列 $p$ 至少需要操作多少次。倒着来，每次可以把开头或结尾插入到任意位置，求至少需要多少次才能变成 $[1,2,\dots,n]$。

设操作了 $k$ 次后变为 $[1,2,\dots,n]$，那么最多用到 $k$ 个数，剩下 $n-k$ 个数一定是连续且递增的，记 $l$ 为 $p$ 最长递增的连续子段，容易通过 $k\le n-l$ 和 $k\ge n-l$ 说明最少操作次数为 $n-l$。于是需要对于每个 $k$，计数 $l\ge n-k$ 的方案数。下面令 $d= n-k$。

先取补集，转化为 $l<d$ 的方案数，把排列划分为若干极长段，对于长度为 $t$ 的段，设置一个权值 $[t<d]$，那么答案就是 $$\sum\limits_{p}\prod\limits_{t\text{为极长的连续段长度}}[t<d]$$ 现在的难点是难以处理极长，我们考虑对于任意一个长度 $x$ 设计一个权值 $c_x$，然后将极长段 $t$ 的权值设计为 $\sum\limits_{t=l_1+l_2+\dots+l_m,l_i\ge1}\prod c_{l_i}=[t<d]$，那么此时设 $g_t=[t<k]$，$G(x),C(x)$ 分别为 $g,c$ 的 OGF，则由 $g_t=\sum\limits_{i=1}^t g_{t-i}c_i$，有 $G(x)=1+G(x)C(x)$，而 $G(x)=\frac{1-x^d}{1-x}$，故 $$C(x)=\frac{x-x^d}{1-x^d}=x+x^{d+1}+x^{2d+1}+\dots-x^{d}-x^{2d}-x^{3d}-\dots$$ 即 $$c_x=\begin{cases}1&x\equiv1\pmod d\\-1&x\equiv0\pmod d\\0&\text{otherwise}.\end{cases}$$ 对于一个划分 $l_1+l_2+\dots+l_m=n$，权值为 $\prod c_{l_i}$，贡献为权值再乘上每一段都递增的排列数，这样就把极长给去掉了。

而对于一种划分，方案数显然为 $\binom{n}{l_1,l_2,\dots,l_m}$，于是考虑 $c_i$ 的 EGF $\hat C(x)$，所求即 $$[\frac{x^n}{n!}]\frac{1}{1-\hat C(x)}$$ 直接多项式求逆即可做到 $\mathcal{O}(n^3\log n)$。

而 $\hat C(x)$ 中非零的项只有 $\mathcal{O}(\frac nd)$ 个，所以递推算出 $A(x)=\frac1{1-\hat C(x)}$ 的系数只需要 $\mathcal{O}(\frac{n^2}d)$，于是总复杂度 $\mathcal{O}(n^2\log n)$。