Problem Description

The $N$ residents of Line Town are standing in a line. Initially, from left to right, their happiness values are $h_{1}, h_{2}, \ldots, h_{N}$.

You are the mayor of Line Town, and you are carrying out your plan called "Community, Candy, and Organization" (CCO). Therefore, you have the power to swap residents' positions. In one swap, you may swap two adjacent residents in the line. However, this swap will flip (negate) the happiness values of both residents.

You want to know whether it is possible to perform some swaps so that the residents' happiness values, from left to right, are in non-decreasing order. If it is possible, output the minimum number of swaps required.

Input Format

The first line contains an integer $N$.

The second line contains $N$ integers $h_{1}, \ldots, h_{N}$, representing the residents' happiness values from left to right.

Output Format

Output one integer on a single line: the minimum number of swaps. If the task is impossible, output $-1$.

6
-2 7 -1 -8 2 8

3

4
1 -1 1 -1

-1

Hint

Sample Explanation 1

You can perform $3$ swaps as follows:

• Swap the 2nd and 3rd residents, and the happiness values become $[-2,1,-7,-8,2,8]$.
• Swap the 4th and 5th residents, and the happiness values become $[-2,1,-7,-2,8,8]$.
• Swap the 3rd and 4th residents, and the happiness values become $[-2,1,2,7,8,8]$.

The residents are now in non-decreasing order of happiness values as required. It is impossible to achieve a non-decreasing arrangement with fewer than $3$ swaps.

Sample Explanation 2

There is no sequence of swaps that can make the residents arranged in non-decreasing order of happiness values.

Constraints

For all testdata, $1 \leq N \leq 5\times 10^5$, $-10^{9} \leq h_{i} \leq 10^{9}$.

• Additional Constraint A: For all $i$, $\left|h_{i}\right| = 1$.
• Additional Constraint B: For all $i$, $\left|h_{i}\right| \leq 1$.
• Additional Constraint C: For all $i \neq j$, $\left|h_{i}\right| \neq\left|h_{j}\right|$.

Translated by ChatGPT 5