Haircut Inversions

Farmer John is tired of dealing with his unruly hair and decides to get a haircut. He has a row of (N) hairs, where the (i)-th hair initially has a length of (A_i) micrometers (with (0 \le A_i \le N)). In an ideal world, he would like his hair to have strictly increasing lengths. Thus, he defines the "messiness" of his hair as the number of inversion pairs. An inversion pair is defined as a pair ((i,j)) such that (i < j) and (A_i > A_j).

For each integer (j = 0, 1, \ldots, N-1), Farmer John performs the following procedure: for every hair whose length is greater than (j), he reduces its length down to exactly (j). He then wants to compute the resulting inversion count of this modified hair array. Your task is to help Farmer John determine the inversion count after each haircut adjustment.

inputFormat

The first line of input contains a single integer (N), the number of hairs. The second line contains (N) space-separated integers (A_1, A_2, \dots, A_N), where (A_i) represents the initial length of the (i)-th hair.

outputFormat

Output (N) lines. The (j)-th line (starting from (j = 0)) should contain a single integer representing the inversion count of the hair array after reducing all hair lengths that are greater than (j) to (j).

sample

3
0 1 2

0
0
0