플레이리스트 정렬

면접 대비

시간 제한1초메모리 제한1024 MB

요약

인접한 두 곡의 위치를 바꾸는 방식으로 N개의 곡 길이를 오름차순으로 정렬하는 데 필요한 최소 교환 횟수를 구합니다.

문제

여러분의 플레이리스트에는 길이가 서로 다른 곡 $N$ 개가 주어진 순서대로 들어 있습니다. 목록을 짧은 곡이 앞에, 긴 곡이 뒤에 오도록 정렬하려고 합니다.

목록을 정렬하는 데 필요한 자리 바꿈의 최소 횟수는 얼마입니까? 자리 바꿈 한 번은 인접한 두 곡을 골라 위치를 맞바꾸는 것입니다.

그림 윗줄은 곡들의 초기 순서이고, 화살표는 목록을 정렬하는 데 필요한 자리 바꿈을 나타냅니다. 아랫줄은 정렬된 결과입니다.

첫 줄에 곡의 개수 $N$ ( $1 \le N \le 1000$ )이 주어진다. 이어서 $N$ 개의 줄에 곡의 길이 $l$ ( $1 \le l \le 1000$ )이 한 줄에 하나씩 주어진다. 모든 곡의 길이는 서로 다르다.

플레이리스트를 정렬하는 데 필요한 자리 바꿈의 최소 횟수를 한 줄에 출력한다.