고집스러운 가마 때문에 지친 농부 존은 머리를 자르기로 했다. 그의 머리카락은 일렬로 놓인 \(N\)개의 가닥으로 이루어져 있으며, \(i\)번째 가닥의 처음 길이는 \(A_i\) 마이크로미터이다. 이상적으로는 머리카락의 길이가 단조 증가하기를 바란다. 따라서 농부 존은 머리카락의 "나쁨"을 역전의 개수, 즉 \(i<j\)이고 \(A_i>A_j\)인 순서쌍 \((i,j)\)의 개수로 정의한다.

\(j=0,1,\ldots,N-1\) 각각에 대해, 길이가 \(j\)보다 큰 모든 머리카락을 정확히 \(j\)가 되도록 줄였을 때 머리카락의 나쁨을 구하여라.

(재미있는 사실: 사람의 머리에는 실제로 평균 약 \(10^5\)가닥의 머리카락이 있다!)

입력

첫째 줄에 정수 \(N\)이 주어진다. (\(1\le N\le 10^5\))

둘째 줄에 \(N\)개의 정수 \(A_1,A_2,\ldots,A_N\)이 주어진다. (\(0\le A_i\le N\))

출력

\(j=0,1,\ldots,N-1\) 각각에 대한 머리카락의 나쁨을 순서대로 한 줄에 하나씩 출력한다.

답이 클 수 있으므로 C/C++에서는 long long과 같은 64비트 정수형을 사용해야 할 수 있다.

예제 입력

5
5 2 3 3 0

예제 출력

0
4
4
5
7

출력의 네 번째 줄은 길이가 \(3\)보다 큰 머리카락을 길이 \(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\)의 다섯 개이다.

서브태스크

출처

USACO 2020 US Open Contest, Gold, Problem 1. Haircut