Ultra-QuickSort

이 문제에서는 특정한 정렬 알고리즘을 분석해야 합니다. 이 알고리즘은 서로 다른 정수 $n$개로 이루어진 수열을, 인접한 두 원소를 교환(swap)하는 연산만 반복하여 오름차순으로 정렬합니다. 예를 들어 수열 9, 1, 0, 5, 4는 0, 1, 4, 5, 9로 정렬됩니다.

주어진 입력 수열을 오름차순으로 정렬하기 위해 Ultra-QuickSort가 수행해야 하는 교환 연산의 최소 횟수를 구하세요.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스의 첫 줄에는 입력 수열의 길이를 나타내는 정수 $n$ ($n < 500{,}000$)이 주어집니다. 이어지는 $n$개의 줄에는 각각 수열의 $i$번째 원소 $a_i$ ($0 \le a_i \le 999{,}999{,}999$)가 한 줄에 하나씩 주어집니다. 한 테스트 케이스 안의 정수들은 모두 서로 다릅니다. 입력은 길이가 $n = 0$인 수열로 끝나며, 이 수열은 처리하지 않습니다.

각 입력 수열에 대해, 그 수열을 오름차순으로 정렬하는 데 필요한 교환 연산의 최소 횟수 $op$를 한 줄에 하나씩 출력합니다.