머리카락 자르기

고집 센 삐침머리에 지친 Farmer John이 머리를 자르기로 했다. 그는 $N$ ($1\le N\le 10^5$) 가닥의 머리카락을 일렬로 가지고 있고, $i$번째 가닥의 처음 길이는 $A_i$ 마이크로미터이다 ($0\le A_i\le N$). 이상적으로는 머리카락 길이가 단조 증가하기를 바라므로, 그는 머리카락의 "나쁨"을 역전 수, 즉 $i < j$이고 $A_i > A_j$인 쌍 $(i,j)$의 개수로 정의한다.

각 $j=0,1,\ldots,N-1$에 대해, FJ는 길이가 $j$보다 큰 모든 가닥을 정확히 $j$로 줄였을 때의 머리카락 나쁨을 알고 싶어 한다.

(재미있는 사실: 평균적인 사람의 머리에는 정말로 약 $10^5$개의 머리카락이 있다!)

첫째 줄에 $N$이 주어진다.

둘째 줄에 $A_1,A_2,\ldots,A_N$이 주어진다.

각 $j=0,1,\ldots,N-1$에 대해 FJ의 머리카락 나쁨을 한 줄에 하나씩 출력한다.

이 문제에서 다루는 정수의 크기가 크므로 64비트 정수형(예: C/C++의 "long long")이 필요할 수 있다.

출력의 넷째 줄은 FJ의 머리카락을 길이 3으로 줄였을 때의 역전 수를 나타낸다. 이때 $A=[3,2,3,3,0]$에는 다섯 개의 역전이 있다: $A_1>A_2,\,A_1>A_5,\,A_2>A_5,\,A_3>A_5,$ 그리고 $A_4>A_5$.