문제
범수는 새로운 정렬 알고리즘을 만들어내고, 여기에 '울트라-퀵 소트'라는 이름을 붙였다.
이 알고리즘은 인접한 두 수를 서로 바꿔서 주어진 수열을 오름차순으로 정렬한다.
수열이 주어지면 그것을 정렬하기 위해 수들을 최소 몇 번 교환해야 하는지 계산해서, '울트라-퀵 소트'가 별로 쓸 일이 없다는 것을 범수에게 알려주자.
입력
첫 줄에 수열의 크기 n(n<=500,000)이 입력된다.
이후 n개의 줄에 수열의 각 원소(0≤a[i]＜10억)가 차례대로 주어진다.
단, 데이터의 70%는 n이 10,000보다 작다.
출력
첫 줄에 필요한 교환 연산의 수를 출력한다.
예제
5
13
3
2
9
6
6
태그
출처
Waterloo local 2005
로그인해야 코드를 작성할 수 있어요.