Smaller Ones Before Me — Solution & Editorial

Back to the Problem

Coordinate-compress the values and sweep left to right with a Fenwick tree: query the prefix below the current rank, then insert it.

Complexity: O(N log N)