시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB999100.000%

문제

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 ≤ 106), oznaczającą liczbę kwadratowych pól. Kolejny wiersz zawiera n liczb całkowitych a1, a2, ..., an (1 ≤ ain), gdzie ai 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.

예제 입력 1

5
3 4 1 5 2

예제 출력 1

1

힌트

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