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

Limits: 2 sec., 512 MiB

Черепашки намішали \(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\).

Input

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

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

Output

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

Constraints

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

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

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

Samples

Input (stdin) сopy	Output (stdout) сopy
3 3 2 1	1

Input (stdin) сopy	Output (stdout) сopy
6 1 4 5 6 2 3	2

Notes

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