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

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

2 секунди
512 мегабайтів
Середня

Черепашки намішали порцій лимонаду. У кожну порцію поклали різну кількість цукру: порція з 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 унікальні.

Вихідні дані

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

Приклади

Приклад

Loading
Loading

Приклад 1

Loading
Loading

Примітка

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