아이들

운동장에 폭이 $1$이고 길이가 $n$인 직사각형을 그린 뒤, 이를 $n$개의 정사각형 칸으로 나눕니다. 각 칸에는 $1$부터 $n$까지의 자연수가 하나씩 적혀 있으며 모든 값이 서로 다릅니다 (즉 $1$부터 $n$까지의 순열입니다). 처음에는 각 칸마다 아이가 한 명씩 서 있습니다. $1$분마다 모든 아이는 자신이 지금 서 있는 칸에 적힌 번호의 칸으로 이동합니다.

이 놀이에 싫증이 난 아이들은 다른 문제를 고민합니다. 놀이를 계속하는 동안 모든 아이가 결국 모든 칸을 한 번씩 밟게 만들고 싶습니다. 이를 위해 서로 이웃한 두 칸 (한 줄 안에서 바로 옆에 붙어 있는 두 칸)에 적힌 숫자를 맞바꿀 수 있습니다. 숫자를 다시 쓰는 데는 시간이 걸리므로 바꾸는 횟수를 최소로 하려고 합니다. 필요한 최소 교환 횟수를 구하세요.

첫째 줄에 정사각형 칸의 개수를 나타내는 정수 $n$ ($1 \le n \le 10^6$)이 주어집니다. 둘째 줄에는 $n$개의 정수 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)이 주어지며, $a_i$는 $i$번째 칸에 적힌 숫자입니다. 모든 값은 서로 다르므로 $1$부터 $n$까지의 순열을 이룹니다.

아이들이 해야 하는 최소 교환 횟수를 정수 하나로 출력합니다.

$n = 5$이고 칸에 적힌 수가 $3\ 4\ 1\ 5\ 2$인 경우에는 $3$번 칸과 $4$번 칸의 숫자를 맞바꾸는 것으로 충분합니다. 그러면 $1$번 칸에서 출발한 아이는 $1 \to 3 \to 5 \to 2 \to 4 \to 1$ 순서로 이동하여 모든 칸을 밟게 됩니다. 따라서 이 경우 최소 교환 횟수는 $1$입니다.