排列的字典序跳转 — 题解¶
出题人解法：降序后缀与阶乘分块跳跃。Codex（GPT-6）整理循环语义、动态存储、证明与验证，并补充 Lehmer 数字方案。
从排列块的末尾跳转¶
固定前缀后，剩下 \(s\) 个不同元素共有 \(s!\) 个排列。按首元素从小到大，每一种选择对应一个连续的等大块。
从右向左扫描位置 \(i\) ，保持右侧 \(s=n-i\) 个数已经降序排列。此时位于当前前缀块的最后一项。设右侧有 \(g\) 个数比 \(a_i\) 大；它们是降序后缀最前面的 \(g\) 项。整个后缀 \([i,n]\) 的最后排列比当前恰晚 \(g\cdot s!\) 步。
若剩余步数足够，减去这个数，将 \(a_i\) 向右移动到这些较大元素之后，得到更长的降序后缀，继续向左。若 \(g=0\) ，不用交换就已经满足不变量。
在某个块内部落点¶
若剩余步数小于 \(g\cdot s!\) ，先消耗一步进入下一个首元素块的第一项。然后还可以完整跨过
个块。于是选择右侧第 \(q+1\) 小的、更大的数作为新的 \(a_i\) .反转降序后缀为升序，与选定元素交换，再把换入的较小元素向左插入正确位置，使余下后缀保持升序。剩余步数变成 \((k-1)\bmod s!\) .
现在是一个按字典序排名还原的子问题。对升序后缀，首元素取第 \(\lfloor k/s!\rfloor+1\) 小的数；余数用于下一位。实现以交换和插入维护升序。只有足够小的阶乘对应非零数字。
本题 \(12!\le2^{31}-1<13!\) ，因此只存到 \(12!\) .右侧超过 12 项时，完整块大于全部剩余步数，商必为零；不用计算大阶乘。降序排列后再走一步回到升序排列。若 \(n\le12\) ，先对 \(n!\) 取余；否则 \(k<n!\) ，最多环绕一次。
正确性¶
降序后缀不变量把当前排列定位在一个块的末尾，计算出的 \(g\cdot s!\) 是到扩大后缀末尾的精确距离，完整跳跃不遗漏落点。不能整段跳过时，先跨边界再按整块商选择首元素，余数恰为目标在剩余后缀内的排名；升序还原逐位实现该排名。最终边界的一步环绕也符合题意，故输出正是所需第 \(k\) 个后继。
复杂度与取舍¶
设 \(K\) 为允许的最大步数，\(D\) 为满足 \(D!>K\) 的最小正整数；本题 \(D=13\) .扫描、至多一次长后缀反转和插入为 \(O(n)\) ，短尾的操作总计 \(O(D^2)\) .每组时间 \(O(n+D^2)\) ，空间 \(O(n+D)\) ；最多两次调用不改变此界。所有组的输入输出总量由总长度限制。
默认使用 std.cpp。树状数组补充方案 更直接地表示排名，但为 \(O(n\log n)\) ，本机正式压力超过 0.5 秒时限，作为正确备用方案与交叉验证程序。