Tired of his stubborn cowlick, Farmer John decides to get a haircut. He has \(N\)
(\(1\le N\le 10^5\)) strands of hair arranged in a line, and strand \(i\) is
initially \(A_i\) micrometers long (\(0\le A_i\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)\) such that \(i < j\) and
\(A_i > A_j\).

For each of \(j=0,1,\ldots,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 \(10^5\) hairs!)

Problem credits: Dhruv Rohatgi

SCORING

• Test case 2 satisfies \(N\le 100.\)
• Test cases 3-5 satisfy \(N\le 5000.\)
• Test cases 6-13 satisfy no additional constraints.

Problem credits: Dhruv Rohatgi

The first line contains \(N\).

The second line contains \(A_1,A_2,\ldots,A_N.\)

For each of \(j=0,1,\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++).

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > US Open > Gold