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

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

2 seconds
512 megabytes
Medium

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

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

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

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

Input

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

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

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

1 \le p_i \le n,

усі p_i унікальні.

Output

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

Examples

Example

Loading
Loading

Example 1

Loading
Loading

Note

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