Colder Days Ahead

A weather log holds one temperature per day. For each day, the forecaster wants to know how many of the later days in the log were strictly colder.

Write count_smaller_after(temps) that returns a list counts of the same length, where counts[i] is how many numbers to the right of temps[i] are strictly smaller than temps[i].

Examples

count_smaller_after([5, 2, 6, 1])
# returns [2, 1, 1, 0]

count_smaller_after([3, 3, 1])
# returns [1, 1, 0]

count_smaller_after([1, 2, 3])
# returns [0, 0, 0]

In the first example 5 has two smaller numbers after it (2 and 1), 2 and 6 have one each, and nothing comes after 1. In the second, an equal number is not smaller.

Constraints

• 0 <= len(temps) <= 100,000
• Every number is a whole number between -10^9 and 10^9
• Comparing every pair of numbers is far too slow at this size.