멋쟁이 현서는 오늘 미용실에서 머리를 자르려고 한다.

현서의 머리에는 n개의 머리카락이 있는데, 각 머리카락 길이를 왼쪽부터 오른쪽까지 차례로 A_1, A_2, \cdots A_n 라고 하자. 놀랍게도 현서의 머리카락 길이는 모두 n이하이다.

오늘 현서가 원하는 헤어스타일은 제일 왼쪽에 있는 머리카락부터 오른쪽으로 진행할 때, 머리카락 길이가 오름차순으로 정렬되는 스타일이다.

그러므로, 현서는 i \lt j 인데, A_i \gt A_j 를 만족하는 모든 머리카락 쌍의 개수를 머리스타일의 “불규칙 지수”라고 정의하기로 하였다.

현서는 상남자이기 때문에, 다음과 같은 이발 방식을 사용한다.

- 바리깡에 길이 T의 탭을 끼우고, 모든 머리카락을 밀어버린다. 이 때 길이가 T보다 긴 모든 머리카락의 길이는 T가 된다. 그대로 이발을 종료한다.

현서는 머리가 너무 짧아지는 것도 싫고, 불규칙 지수가 너무 많아지는 것도 싫기 때문에, 모든 T값에 대한 불규칙 지수를 계산하려고 한다. 이를 도와주는 프로그램을 작성하라.

미용 timer 1s memory 256MB

미용 1s 256MB