#209HardRange Queries· Fenwick Tree with Coordinate Compression

Smaller Ratings to the Right

A streaming service lists customer ratings in the order they were submitted. For a quality report it wants, for each rating, the number of **later** ratings that are **strictly lower**. A rating followed by many lower ones suggests that opinions are dropping, which helps the team spot declining trends early. Given the array `ratings`, return an array `counts` of the same length where `counts[i]` is the number of indices `j > i` with `ratings[j] < ratings[i]`. Comparing every pair is quadratic and too slow for large inputs; an O(n log n) method is expected.

Input format

`ratings`: the ratings in submission order.

Output format

An array where entry i counts the later ratings strictly smaller than ratings[i].

Examples

Input: ratings = [5, 2, 6, 1]

Output: [2, 1, 1, 0]

After 5 come 2 and 1 (smaller): 2. After 2 comes 1: 1. After 6 comes 1: 1. After 1 nothing: 0.

Input: ratings = [3, 3, 3]

Output: [0, 0, 0]

Equal ratings are not strictly smaller, so every count is 0.

Input: ratings = [9, 7, 5, 3]

Output: [3, 2, 1, 0]

A strictly decreasing list has every later rating smaller: 3, 2, 1, 0.

Constraints

1 <= ratings.length <= 10^5
-10^4 <= ratings[i] <= 10^4

#fenwick-tree
#binary-indexed-tree
#coordinate-compression
#merge-sort
#counting