A race report lists n runners in bib order, each with a performance value. For every runner, count how many of the runners listed after them (to their right in the list) have a strictly smaller value than they do.
Output these counts, one per runner, in the original bib order. The intended approach obtains all counts together while performing a single merge sort that remembers each value's original position.
Input format
Line 1: an integer n, the number of runners.
Line 2: n space-separated integers, the performance values in bib order.
Output format
A single line of n space-separated integers: for each runner (in bib order), the number of strictly-smaller values that appear later in the list.
Constraints
- 1 <= n <= 100000
- 0 <= each value <= 1000000000