## USACO 2020 US Open Contest, Gold

## Problem 1. Haircut

Contest has ended.

**Log in to allow submissions in analysis mode**

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$.

Contest has ended. No further submissions allowed.
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!)

#### INPUT FORMAT (file haircut.in):

The first line contains $N$.The second line contains $A_1,A_2,\ldots,A_N.$

#### OUTPUT FORMAT (file haircut.out):

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++).

#### SAMPLE INPUT:

5 5 2 3 3 0

#### SAMPLE OUTPUT:

0 4 4 5 7

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$.

#### 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