Dzieci
Limit pamięci: 32 MB
Dzieci bawią się w pewną zabawę. Na boisku narysowany jest prostokąt
jednostkowej szerokości i długości , podzielony na kwadratowych pól.
Na każdym polu wpisana jest liczba naturalna z przedziału od do ,
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.
Wejście
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą
(), oznaczającą liczbę kwadratowych pól.
Kolejny wiersz zawiera liczb całkowitych (),
gdzie oznacza liczbę wpisaną w -tym kwadratowym polu.
Wyjście
Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą,
równą minimalnej liczbie zamian, które powinny dokonać dzieci.
Przykład
Dla danych wejściowych:
5
3 4 1 5 2
poprawną odpowiedzią jest:
1
Wyjaśnienie do przykładu: Wystarczy zamienić miejscami pola numer 3 i 4. Wtedy dzieci będą się
zamieniać następująco: .
Autor zadania: Jacek Tomasiewicz.