让序列不再有序 2

不同的重排列中恰有一个有序序列。维护每个前缀的重排列数 $W$。加入第 $i$ 个元素后，设其值的新频率为 $c$，更新 $W\leftarrow W\cdot i/c$，最后输出 $W-1$。前缀的重排列数不会超过整体，因此 $W\leq10^{12}+1$。乘法中间值不超过 $(10^{12}+1)10^5<1.01\cdot10^{17}$，可用有符号64位整数。使用映射表的时间为 $O(N\log N)$。