Smaller Ones Before Me

Difficulty: 1700 3500 ms 128 MB

fenwick sorting

For each position, print how many EARLIER elements are strictly smaller than it.

Input: the first line has N; the second line has N integers.

Output: N integers: the count of smaller predecessors per position.

Constraints:

• 1 ≤ N ≤ 10⁵
• |a_i| ≤ 10⁹

Sample Tests

5
3 1 4 1 5

0 0 2 0 4

2
2 2

0 0

Read the Editorial