Count of Smaller Numbers After Self

Problem statement

A ranking analyst examines scores in their recorded order. For each score, the report needs the number of later scores that are strictly smaller, so it can measure how many subsequent entries that score exceeds. Your task Return an array where answer[i] counts indices j greater than i with nums[j] less than nums[i]. Target O(n log n) time. Important details Equal values are not smaller. Count positions rather than distinct values, so repeated smaller scores each contribute. The last entry always has count zero. A modified merge sort or a Fenwick tree with compressed ranks avoids quadratic scanning. Worked example For [5, 2, 6, 1], the counts are [2, 1, 1, 0]: 5 exceeds later values 2 and 1, while 2 and 6 each exceed only 1.

Input format

The first line contains n. The next line contains n space-separated integers; for n = 0 this line may be empty.

Output format

Print the resulting values in order, separated by spaces. Print EMPTY if there are no values.

Constraints

1 <= n <= 100000; -10000 <= values <= 10000.

Sample input

4
5 2 6 1

Sample output

2 1 1 0