eolymp
bolt
Try our new interface for solving problems
Problems

Haircut

Haircut

Time limit 1 second
Memory limit 128 MiB

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 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 (i, j) such that i < j and a[i] > a[j].

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 10^5 hairs!)

Input data

The first line contains n (1n10^5). The second line contains a[1], a[2], ..., a[n] (0a[i]n).

Output data

For each of j = 0, 1, ..., n1, 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: a[1] > a[2], a[1] > a[5], a[2] > a[5], a[3] > a[5] and a[4] > a[5].

Examples

Input example #1
5
5 2 3 3 0
Output example #1
0
4
4
5
7
Source 2020 USACO US Open, Gold