Haircut | Code Joint

Tired of his stubborn cowlick, Farmer John decides to get a haircut. He has $N$ ( $1 \leq N \leq 1 0^{5}$ ) strands of hair arranged in a line, and strand $i$ is initially $A_{i}$ micrometers long ( $0 \leq A_{i} \leq N$ ). Ideally, he wants his hair to be monotonically increasing in length, so he defines the "badness" of his hair as the number of inversions: pairs $(i, j)$ such that $i < j$ and $A_{i} > A_{j}$ .

For each of $j = 0, 1, \dots, N - 1$ , FJ would like to know the badness of his hair if all strands with length greater than $j$ are decreased to length exactly $j$ .

(Fun fact: the average human head does indeed have about $1 0^{5}$ hairs!)

The fourth line of output describes the number of inversions when FJ's hairs are decreased to length 3. Then $A = [3, 2, 3, 3, 0]$ has five inversions: $A_{1} > A_{2}, A_{1} > A_{5}, A_{2} > A_{5}, A_{3} > A_{5},$ and $A_{4} > A_{5}$ .

SCORING:

Test case 2 satisfies $N \leq 100.$
Test cases 3-5 satisfy $N \leq 5000.$
Test cases 6-13 satisfy no additional constraints.

Problem credits: Dhruv Rohatgi

Source: USA Computing Olympiad.

Input Format

The first line contains $N$ .

The second line contains $A_{1}, A_{2}, \dots, A_{N} .$

Output Format

For each of $j = 0, 1, \dots, N - 1$ , output the badness of FJ's hair on a new line.

Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

Sample Input

5 5 2 3 3 0

Sample Output

0 4 4 5 7

Submit

Language