8681번 - Dzieci 다국어

Dzieci bawią się w pewną zabawę. Na boisku narysowany jest prostokąt jednostkowej szerokości i długości n, podzielony na n kwadratowych pól. Na każdym polu wpisana jest liczba naturalna z przedziału od 1 do n, każda o innej wartości. Początkowo w każdym z kwadratów stoi jedno dziecko. Co minutę każde z nich przechodzi na pole o numerze napisanym na polu, na którym obecnie stoi.

Po pewnym czasie dzieci znudziły się tą zabawą i zastanawiają się nad innym problemem. Chciałyby pozmieniać miejscami niektóre liczby, napisane na dwóch sąsiednich kwadratach, tak aby każde dziecko podczas całej zabawy stało na każdym możliwym polu. Przerysowywanie literek zajmuje trochę czasu, więc zależy im, aby tych zmian było jak najmniej.

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą n (1 ≤ n ≤ 10⁶), oznaczającą liczbę kwadratowych pól. Kolejny wiersz zawiera n liczb całkowitych a₁, a₂, ..., a_n (1 ≤ a_i ≤ n), gdzie a_i oznacza liczbę wpisaną w i-tym kwadratowym polu.

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą, równą minimalnej liczbie zamian, które powinny dokonać dzieci.

Wystarczy zamienić miejscami pola numer 3 i 4. Wtedy dzieci będą się zamieniać następująco: 1 → 3 → 5 → 2 → 4 → 1.