Черепашки намішали порцій лимонаду. У кожну порцію поклали різну кількість цукру: порція з p_i = 1 — найменш солодка, а p_i = n — найсолодша. Отже, послідовність p_1, p_2, \dots, p_n є перестановкою чисел від до .
Рафаель запропонував для кожної пари індексів i < j спробувати почергово ковтнути спочатку порцію , а потім порцію . Черепашкам стане неприємно тоді й тільки тоді, коли напій стає менш солодким, тобто p_i > p_j. Кожна така пара називається поганою парою.
Леонардо хоче розділити всі погані пари порівну між чотирма черепашками, тобто добитися, щоб загальна кількість поганих пар стала кратною . Для цього за одну операцію можна вибрати будь-які дві порції і поміняти їх місцями, тобто поміняти два елементи перестановки.
Знайдіть мінімальну кількість таких операцій, щоб кількість поганих пар у перестановці стала кратною .
У першому рядку задано одне число — кількість порцій, що замішали черепашки.
У другому рядку задано цілих чисел p_i — перестановка, що описує солодкість напоїв.
2 \le n \le 5 \cdot 10^5,
1 \le p_i \le n,
усі p_i унікальні.
Виведіть одне ціле число — мінімальну кількість операцій, щоб досягти мети.
Example
Example 1
Зауважте, що загальна кількість поганих пар може збільшитись, основне аби вони могли їх чесно розподілити.