25577번 - 열 정렬정렬 정

열정이 가득한 김정렬은 항상 배열을 오름차순 정렬하려고 하는 강박증이 있다.

하지만 너무 열정적으로 정렬한 나머지 제대로 정렬하지 못하는 경우가 생긴다.

김정렬의 친구로서, 정렬이가 눈치채기 전에 다시 정렬시켜주려고 한다. 하지만 배열을 너무 많이 바꿀 경우 정렬이가 눈치를 채게 되고, 정렬이는 낙담할 것이다.

우리가 배열에 적용할 수 있는 연산은 임의의 두 값을 뽑아서 서로 교환하는 것이다. 정렬이 몰래 정렬하기 위해 최소한으로 필요한 연산 횟수를 구하자.

첫 번째 줄에 배열의 크기 $N(4 ≤ N​ ≤ 100\,000)$이 주어진다.

그다음 줄에 배열의 원소 $A_1, A_2, \cdots, A_n (-10^9 ≤ A_i ≤ 10^9, i \neq j $ 이면 $ A_i \neq A_j )$ 이 주어진다.

배열의 원소는 모두 정수이다.

배열에 적용할 최소 연산 횟수를 출력한다.