Problem Description

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

As the mayor of Line Town, you are implementing your "Community, Candy, and Organization" (CCO) plan. Therefore, you have the power to swap the positions of residents. In one swap, you can exchange the positions of two adjacent residents, which will invert their happiness values.

You want to know if it is possible to perform some swaps such that the residents' happiness values are in non-decreasing order from left to right. If possible, what is 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 happiness values of the residents from left to right.

Output Format

Output a single integer, which is the minimum number of swaps required. If it is not possible to achieve the task, output $-1$.

Sample Input and Output

Sample Input #1

6
-2 7 -1 -8 2 8

Sample Output #1

3

Sample Input #2

4
1 -1 1 -1

Sample Output #2

-1

Notes

Sample Explanation 1

Three swaps can be performed as follows:

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

The residents are now in the required non-decreasing order of happiness values. No fewer than 3 swaps can achieve this order.

Sample Explanation 2

No sequence of swaps can arrange the residents in non-decreasing order of happiness values.

For all data, $1 \leq N \leq 5 \times 10^5$ and $-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|$.

见题面 Input 部分

见题面 Output 部分