Tired of his stubborn cowlick, Farmer John decides to get a haircut. He has NN (1≤N≤1051≤N≤105) strands of hair arranged in a line, and strand ii is initially AiAi micrometers long (0≤Ai≤N0≤Ai≤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)(i,j) such that i<ji<j and Ai**>AjAi>Aj.For each of j=0,1,…,N−1**j=0,1,…,N−1, FJ would like to know the badness of his hair if all strands with length greater than jj are decreased to length exactly jj.

(Fun fact: the average human head does indeed have about 105105 hairs!)

INPUT FORMAT (file haircut.in):

The first line contains NN.The second line contains A1**,A2**,…,AN**.**A1,A2,…,AN.

OUTPUT FORMAT (file haircut.out):

For each of j=0,1,…,N−1j=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++).

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]A=[3,2,3,3,0] has five inversions: A1>A2,A1**>A5**,A2**>A5**,A3**>A5**,A1>A2,A1>A5,A2>A5,A3>A5, and A4**>A5**A4>A5.

SCORING:

• Test case 2 satisfies N≤**100.**N≤100.
• Test cases 3-5 satisfy N≤**5000.**N≤5000.
• Test cases 6-13 satisfy no additional constraints.