Write count_smaller(nums) -> list[int] where out[i] is the number of indexes j > i with nums[j] < nums[i] (strictly smaller).
count_smaller([4, 1, 3, 1]) # [3, 0, 1, 0]
count_smaller([2, 2, 2]) # [0, 0, 0] (equal isn't smaller)
count_smaller([]) # []
Constraints: len(nums) up to 2 * 10^5, values in [-10**4, 10**4]. The double loop is O(n²); aim for O(n log n).
Show hint
Walk from right to left, so that everything you have already seen is to the right of the current index. You then need a structure over the values seen so far that answers "how many are smaller than x?" and accepts a new value, both in O(log n). (A divide-and-conquer that counts while sorting also works.)