Write compress(xs: list[int]) -> list[int] that replaces every value with its rank among the distinct values of xs, counting from 0: the smallest distinct value becomes 0, the next 1, and so on. Equal values get equal ranks. Return a new list; don't modify xs.
compress([100, 5, 100, 42]) # [2, 0, 2, 1]
compress([-3, 10**12, -3]) # [0, 1, 0]
compress([]) # []
Constraints: len(xs) <= 2·10^5, values anywhere in [-10^18, 10^18].
Aim for O(n log n). Searching a list for every element is O(n·d), where d is the number of distinct values, and fails the large test.
Show hint
this is coordinate compression, used to shrink huge or sparse coordinates into 0..d-1 so they can index an array. Sort the distinct values once, then make each rank lookup O(1).