Lemonade Party

Limits: 2 sec., 512 MiB

This statement was translated automatically from Ukrainian.

The turtles mixed \(n\) portions of lemonade. Each portion has a different amount of sugar: the portion with \(p_i = 1\) is the least sweet, and \(p_i = n\) is the sweetest. Thus, the sequence \(p_1, p_2, \dots, p_n\) is a permutation of the numbers from \(1\) to \(n\).

Raphael suggested that for each pair of indices \(i < j\), they should try taking a sip of portion \(i\) first, and then portion \(j\). The turtles will feel uncomfortable if and only if the drink becomes less sweet, i.e., \(p_i > p_j\). Each such pair \((i, j)\) is called a bad pair.

Leonardo wants to divide all bad pairs equally among the four turtles, i.e., make the total number of bad pairs a multiple of \(4\). To do this, in one operation, you can choose any two portions and swap them, i.e., swap two elements of the permutation.

Find the minimum number of such operations to make the number of bad pairs in the permutation a multiple of \(4\).

Input

The first line contains a single integer \(n\) — the number of portions mixed by the turtles.

The second line contains \(n\) integers \(p_i\) — the permutation describing the sweetness of the drinks.

Output

Output a single integer — the minimum number of operations to achieve the goal.

Constraints

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

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

all \(p_i\) are unique.

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

Note that the total number of bad pairs can increase, the main thing is that they can distribute them fairly.