Description

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!)

Input Format

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

Output Format

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++).

5
5 2 3 3 0

0
4
4
5
7

Hint

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