提供一个比较神秘的解法
除了我估计没人会写这种东西（捂脸
观察一个 almost sorted 的序列，它应当是许多个公差为 −1 的等差序列拼在一起的形式
考虑长度为 n 的 almost sorted 序列的个数 fn，不难得到 fn=1+i=1∑n−1fi，也即 fn=2n−1——因为 n 是当前排列中最大的数，在它的序列之后一定是 ⟨n−1,n−2,n−3⋯⟩ 直到序列末尾（当然最后一个数不一定是 1），在它之前的序列是一个长度小于 n 的 almost sorted 序列。枚举 n 在序列中的位置即得到上式。
然后注意到 k 的范围仅仅是 1018≈260，也就是说当 n 超过 60 的时候最终的序列前面一定是 ⟨1,2,3⋯⟩。于是对前 n−z 位输出 1∼n−z，对后 z 位做一个 z2 暴力依次确定每一个位置的值，其中 z≥60。这部分的复杂度显然是个常数，于是整个算法的时间复杂度为 O(n)。
赛时代码
