Unsorting a Sequence 2

Exactly one distinct rearrangement is sorted. Maintain the number $W$ of rearrangements of each prefix. When inserting element $i$, let its new frequency be $c$ and update $W\leftarrow W\cdot i/c$. Output $W-1$. A prefix has no more rearrangements than the complete multiset, so $W\leq10^{12}+1$. The multiplication is bounded by $(10^{12}+1)10^5<1.01\cdot10^{17}$ and fits signed 64-bit integers. Using a map gives $O(N\log N)$ time.