문제
GodJail(갓재일)은 정렬을 할 줄 모르는 불쌍한 어린 양들을 위해 길이가 N인 수열 A를 정렬하는 함수를 아래와 같이 만들어줬다.
여기서 swap(x, y) 함수는 x, y의 값을 서로 바꾸는 함수이다.
그런데, N이 커지면 swap 함수를 호출하는 횟수가 많아져 정렬하는 데 걸리는 시간이 급격하게 늘어나기 때문에 어린 양들이 곤혹을 치르고 있다.
그러다가 태영이라는 이름의 어린 양이 'bubble_sort 함수를 호출하기 전에
swap(A[x], A[y]) (단, 0 ≤ x < y ≤ N-1) 함수를 한 번 호출하면 정렬하는 데 걸리는 시간이 많이 줄어들지 않을까?' 라는 의문을 제시하였다.
태영이의 등장에 따라 다른 양들이 혼란을 많이 겪고 있다.
GodJail의 제자인 당신이 'swap 함수를 호출하는 횟수의 최솟값'을 구해서 불쌍한 어린 양들에게 태영이의 아이디어가 틀렸다는 것을 알려주자.
입력
첫 번째 줄에는 A의 원소의 수 N이 주어진다. (2 ≤ N ≤ 100,000)
두 번째 줄에는 A[i]가 주어진다. (1 ≤ A[i] ≤ 1,000,000,000)
전체 데이터의 10%는 N ≤ 1,000이며, 전체 데이터의 30%는 N ≤ 3,000이다.
전체 데이터의 80%는 A의 모든 원소의 값이 서로 다르다.
출력
bubble_sort 함수 안에서 swap 함수를 호출하는 횟수의 최솟값을 출력한다.
bubble_sort 함수를 호출하기 전에 반드시 swap(A[x], A[y])를 호출해야 함에 유의하여라.
예제1
입력
5
31795
출력
2
예제2
입력
5
103681
출력
0
예제3
입력
3
123
출력
1
힌트
출처
JOI 2012/2013 본선 5