P6278 [USACO20OPEN] Haircut G

Farmer John is tired of trying to straighten his unruly hair, so he decides to get a haircut. He has a row of $N$ strands of hair, and the $i$-th strand initially has length $A_i$ micrometers ($0 \le A_i \le N$). Ideally, he wants his hair lengths to be monotonically non-decreasing, 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 $j = 0, 1, \ldots, N - 1$, Farmer John wants to know the badness of his hair if all strands with length greater than $j$ are reduced to length $j$. ----- (Fun fact: Humans really do have about $10^5$ hairs on average!)

The first line contains $N$. The second line contains $A_1, A_2, \ldots, A_N$.

For each $j = 0, 1, \ldots, N - 1$, output on a separate line the badness of Farmer John’s hair. ----- **Note that the integer values in this problem may require 64-bit integer storage (for example, “long long” in C/C++).**

#### Sample Explanation: The fourth line of the output describes the number of inversions when Farmer John’s hair lengths are reduced to $3$. $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$. ---- For $100\%$ of the testdata, $1 \le N \le 10^5$. There are $13$ test points in total. Test point $1$ is the sample, and the others satisfy: Test point $2$ satisfies $N \le 100$. Test points $3 \sim 5$ satisfy $N \le 5000$. Test points $6 \sim 13$ have no additional constraints. ----- Problem author: Dhruv Rohatgi. Translated by ChatGPT 5