Haircut

문제

Tired of his stubborn cowlick, Farmer John decides to get a haircut. He has $NN$ ($1\le N\le {10}^{5}1\backslash le\; N\backslash le\; 10^5$) strands of hair arranged in a line, and strand $ii$ is initially $A_{i}A\_i$ micrometers long ($0\le A_i\le N0\backslash le\; A\_i\backslash le\; 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)(i,j)$ such that and $A_i>A_{j}A\_i\; >\; A\_j$.

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

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

입력

The first line contains $NN$.

The second line contains $A_1,A_2,\dots ,A_N\mathrm{.}A\_1,A\_2,\backslash ldots,A\_N.$

출력

For each of $j=0,1,\dots ,N-1j=0,1,\backslash ldots,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++).

힌트

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]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,A\_1>A\_2,\backslash ,A\_1>A\_5,\backslash ,A\_2>A\_5,\backslash ,A\_3>A\_5,$ and $A_4>A_{5}A\_4>A\_5$.

5
5 2 3 3 0

0
4
4
5
7