当且仅当存在一个长度至少为 $n-k$ 的单调子串的排列才是合法的。
计算不存在长度至少为 $n-k$ 的单调子串数量，然后用 $n!$ 减一下就是题目所求的数量。
为了行文方便，后文中用 $k$ 来代替 $n-k-1$，那么就需要求所有单调子串的长度不超过 $k$ 的方案数。

我们可以把一个排列拆成若干单调子串，满足这些单调子串是从左到右贪心拆分的。比如说排列 $2,1,5,3,4$ 的贪心拆分就是 $[2],[1,5],[3,4]$；排列 $4,1,2,3,5$ 的贪心拆分就是 $[4],[1,2,3,5]$。
记 $w_i$ 表示长度为 $i$ 的单调子串的价值，如果令 $w_i=[i\le k]$，那么一个排列合法当且仅当其贪心拆分后的所有子串价值积为 $1$。
记

\[G(x)=\sum_{i=0}^\infty w_ix^i\\\]

筛法（容斥是第一种筛法）有第二种：在一个较大的集合里的元素可以以某种自然的方式赋予系数，使得不想要的元素被消去，只剩下初始的集合。——Richard P. Stanley

$i$ 个数形成一个单调递增的排列只有 $1$ 种方案，因此我们记

\[F(x)=\sum_{i=1}^\infty f_i\times1\times x^i=\sum_{i=1}^\infty f_ix^i\\ \hat F(x)=\sum_{i=1}^\infty f_i\times1\times \frac{x^i}{i!}=\sum_{i=1}^\infty f_i\frac{x^i}{i!}\\\]

其中 $f_i$ 是一个待赋予的系数。

我们要把 $1\sim n$ 拆成若干段，再把每段拼接起来，拆成若干段会产生一个多重集的排列数，我们得用指数生成函数，那么答案就是

\[\sum_{i=0}^\infty\hat F^i(x)= \frac1{1-\hat F(x)}\]

我们从这个式子的组合意义看出，一个长度为 $j$ 的单调子串会被错误划分为若干短的单调子串。比如 $[2],[1,5],[3,4]$ 和 $[2],[1],[5],[3,4]$ 和 $[2],[1,5],[3],[4]$ 和 $[2],[1],[5],[3],[4]$ 都会被这个生成函数枚举到，但后三种是错误划分。
我们得合理分配系数 $f_i$ 使得被划分为若干短的单调子串的计数被消去。
我们关心长度为 $j$ 的单调子串划分出来若干短的单调子串会产生多少贡献，由于已经单调递增，相当于只要划分成若干段，无需多重集的排列数。
采用普通生成函数就可以看出一个长度为 $j$ 的单调子串会被错误划分为若干短的单调子串产生的错误贡献就是

\[[x^j]\left(\sum_{i=0}^\infty F^i(x)-G(x)\right)=[x^j]\left(\frac1{1-F(x)}-G(x)\right)\]

要让错误贡献被消去，即

\[\frac1{1-F(x)}-G(x)=0\]

解得 $F(x)=1-G^{-1}(x)$，有了 $F(x)$ 后对每一项除以阶乘就得到 $\hat F(x)$，最后答案就是上文所说的

\[\sum_{i=0}^\infty\hat F^i(x)= \frac1{1-\hat F(x)}\]