Лимонадна вечірка

Обмеження: 2 сек., 512 МіБ

Черепашки намішали \(n\) порцій лимонаду. У кожну порцію поклали різну кількість цукру: порція з \(p_i = 1\) — найменш солодка, а \(p_i = n\) — найсолодша. Отже, послідовність \(p_1, p_2, \dots, p_n\) є перестановкою чисел від \(1\) до \(n\).

Рафаель запропонував для кожної пари індексів \(i < j\) спробувати почергово ковтнути спочатку порцію \(i\), а потім порцію \(j\). Черепашкам стане неприємно тоді й тільки тоді, коли напій стає менш солодким, тобто \(p_i > p_j\). Кожна така пара \((i, j)\) називається поганою парою.

Леонардо хоче розділити всі погані пари порівну між чотирма черепашками, тобто добитися, щоб загальна кількість поганих пар стала кратною \(4\). Для цього за одну операцію можна вибрати будь-які дві порції і поміняти їх місцями, тобто поміняти два елементи перестановки.

Знайдіть мінімальну кількість таких операцій, щоб кількість поганих пар у перестановці стала кратною \(4\).

Вхідні дані

У першому рядку задано одне число \(n\) — кількість порцій, що замішали черепашки.

У другому рядку задано \(n\) цілих чисел \(p_i\) — перестановка, що описує солодкість напоїв.

Вихідні дані

Виведіть одне ціле число — мінімальну кількість операцій, щоб досягти мети.

Обмеження

\(2 \le n \le 5 \cdot 10^5\),

\(1 \le p_i \le n\),

усі \(p_i\) унікальні.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 3 2 1	1

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
6 1 4 5 6 2 3	2

Примітки

Зауважте, що загальна кількість поганих пар може збільшитись, основне аби вони могли їх чесно розподілити.