$N$ residents of Line Town are standing in a line. Initially, the happiness values of the residents from left to right are $h_1, h_2, \dots, h_N$.

As the mayor of Line Town, you are implementing your "Community, Candy, and Organization" (CCO) plan. Consequently, you have the power to swap the positions of residents. In one swap, you can choose two adjacent residents and swap their positions in the line. However, this swap causes the happiness values of both residents to be negated.

You want to know if it is possible to perform a series of swaps such that the residents' happiness values are in non-decreasing order from left to right. If it is possible, what is the minimum number of swaps required?

Input

The first line contains an integer $N$. The second line contains $N$ integers $h_1, \dots, h_N$, representing the happiness values of the residents from left to right.

Output

Output a single integer representing the minimum number of swaps. If the task is impossible, output $-1$.

Examples

Input 1

6
-2 7 -1 -8 2 8

Output 1

3

Note 1

It is possible to perform 3 swaps as follows: 1. Swap the 2nd and 3rd residents; the happiness values become $[-2, 1, -7, -8, 2, 8]$. 2. Swap the 4th and 5th residents; the happiness values become $[-2, 1, -7, -2, 8, 8]$. 3. Swap the 3rd and 4th residents; the happiness values become $[-2, 1, 2, 7, 8, 8]$.

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

Input 2

4
1 -1 1 -1

Output 2

-1

Note 2

There is no series of swaps that can make the residents' happiness values non-decreasing.

Subtasks

For all data, $1 \le N \le 5 \times 10^5$ and $-10^9 \le h_i \le 10^9$.