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.