레이팅 미적용고집스럽게 뻗친 머리카락에 지친 농부 존은 이발을 하기로 결심했다. 그의 머리카락 \(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\)에 대해, 길이가 \(j\)보다 큰 모든 가닥을 정확히 길이 \(j\)로 잘랐을 때 머리카락의 나쁨이 얼마인지 농부 존은 알고 싶다.
(재미있는 사실: 실제로 평균적인 사람의 머리에는 약 \(10^5\)가닥의 머리카락이 있다!)
문제 제공: Dhruv Rohatgi
배점
- 테스트 케이스 2는 \(N\le 100\)을 만족한다.
- 테스트 케이스 3-5는 \(N\le 5000\)을 만족한다.
- 테스트 케이스 6-13은 추가 제약이 없다.
문제 제공: Dhruv Rohatgi
첫째 줄에 \(N\)이 주어진다.
둘째 줄에 \(A_1,A_2,\ldots,A_N\)이 주어진다.
각 \(j=0,1,\ldots,N-1\)에 대해, 농부 존의 머리카락의 나쁨을 한 줄에 하나씩 출력한다.
이 문제에서 다루는 정수가 커서 64비트 정수 자료형(예: C/C++의 "long long")이 필요할 수 있음에 주의한다.
haircut.in · 출력을 쓸 파일 haircut.out5
5 2 3 3 00
4
4
5
7The 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\).