排序

把连续排序过程看成维护一个大小为 $m$ 的集合。开始时放入 $a_1,\ldots,a_m$，每次取出其中最小值作为下一个 $b_i$，再加入一个新的 $a$；最后把剩余的 $m$ 个数从小到大取出。因此 $b_i$ 就是 $a_1,\ldots,a_{\min(i+m-1,n)}$ 中，尚未在 $b_1,\ldots,b_{i-1}$ 出现的最小值。若 $b_i$ 不是前缀最大值，那么它的位置实际上已经唯一确定为 $a_{i+m-1}=b_i$。把所有这样的 $b_i$ 以及对应的 $a$ 位置删掉后，问题规模变小，而 $m,k$ 不变；剩余的 $b$ 严格递增。把剩余元素按大小重新编号后，只需解决 $b_i=i$ 的情形。

设缩小后的规模为 $N$。值 $i$ 必须在输出它之前进入集合，所以它在原排列中的位置需要满足 $\operatorname{pos}(i)\le\min(i+m-1,N)$。这个条件也是充分的。

从小到大放置值 $i$。此前 $1,\ldots,i-1$ 已占用 $i-1$ 个合法位置，所以 $i$ 的可选位置数为 $\min(m,N-i+1)$。因此总方案数为$F(N)=\prod_{t=1}^{N}\min(m,t)$。若第一位取最小的 $1$，删掉这一位和值 $1$ 后，剩下的仍是同一个问题，方案数为 $F(N-1)$。所以只要 $F(N-1)\ge k$，第一位一定取 $1$。

设 $S$ 是满足 $F(S)\ge k$ 的最小整数，那么前 $N-S$ 位一定为 $1,2,\ldots,N-S$，只需对最后 $S$ 位做字典序反排名。由于 $k\le10^{18}$，当 $m\ge2$ 时有 $F(S)\ge2^{S-1}$，因此 $S\le61$；若 $m=1$，只有唯一方案。对于剩余的 $S$ 个位置，设当前处理位置为 $p$，剩余值从小到大为 $v_1<v_2<\cdots<v_t$。若不限制下一位具体填谁，按值从小到大放置时，$v_j$ 最晚只能放到 $\min(S,v_j+m-1)$，而此前已有 $p-1$ 个位置被占，另有 $j-1$ 个更小剩余值会先占位置，所以它的可选位置数为$\min(S,v_j+m-1)-(p-1)-(j-1)$。这些数相乘就是当前状态的方案数。于是枚举当前位置填哪个剩余值，计算该分支的后续方案数，就可以普通贪心反排名。

总时间复杂度为 $O(n+S^3)$，实际可视为 $O(n)$，空间复杂度为 $O(n)$。