考虑从小到大加数，发现无论之前的排列是怎么样，插入 $n+1$ 的贡献都是 $0,1,\ldots,n$ 的排列。

假设插入前有 $c$ 个下降的位置。如果插入在末尾，贡献是 $0$。如果插入在下降的位置之间，那么贡献就是后缀中（包含插入位置）有多少个下降的位置，所以依次是 $1,2,\ldots,c$。如果插入在上升的位置之间，那么贡献是当前下标加上后缀中有多少个下降的位置，注意到第 $i$ 个上升位置的下标就是 $i$ 加上前缀中有多少个下降的位置，所以这样的贡献依次是 $c+1,c+2,\ldots,n$。

所以也就是要求 $\prod_{i=1}^n\frac{1-x^n}{1-x}$ 的第 $k$ 项次数，$O(n^3)$ DP 即可。