Haircut
Haircut
Tired of his stubborn cowlick, Farmer John decides to get a haircut. He has n strands of hair arranged in a line, and strand i is initially ai
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 (i, j) such that i < j and ai
> aj
.
For each of j = 0, 1,..., 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 105
hairs!)
Input
The first line contains n (1 ≤ n ≤ 105
). The second line contains a1
, a2
, ..., an
(0 ≤ ai
≤ n).
Output
For each of j = 0, 1, ..., 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++).
Example
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] has five inversions: a1
> a2
, a1
> a5
, a2
> a5
, a3
> a5
and a4
> a5
.
5 5 2 3 3 0
0 4 4 5 7