Haircut#10310
Tired of his stubborn cowlick, Farmer John decides to get a haircut. He has strands of hair arranged in a line, and strand is initially a_i micrometers long. 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 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 are decreased to length exactly .
(Fun fact: the average human head does indeed have about 10^5 hairs!)
The first line contains (1 \le n \le 10^5). The second line contains a_1, a_2, \ldots, a_n (0 \le a_i \le 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++).
5 3 2 3 3 0 0 4 4 5 5
Esempio 1
The fourth line of output describes the number of inversions when FJ's hairs are decreased to length . 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.