CCO Town Happiness

In the town of Lineville, there are N residents standing in a line with happiness values h₁, h₂, ..., h_N from left to right. As the mayor implementing the "Community, Candy and Organization" (CCO) plan, you have the power to swap adjacent residents. In a single swap, you may exchange two adjacent residents, but as a consequence, both of their happiness values are negated.

Your task is to determine whether it is possible to perform a sequence of adjacent swaps such that the final arranged happiness values (after any negations incurred by swaps) are in non-decreasing order. If it is possible, you must compute the minimum number of swaps required; otherwise, output -1.

Important details:

• The residents are initially numbered 1 through N from left to right, with happiness values h₁, h₂, ..., h_N.
• In one swap, you may only exchange two adjacent residents. When you swap the residents originally at positions i and i+1, both of their happiness values become negated.
• If a resident originally with happiness value h is moved from position i to position j via adjacent swaps, the number of swaps it participates in is exactly |i − j|. Hence its final happiness value becomes h if |i − j| is even, and −h if |i − j| is odd.
• The final arrangement is determined by a permutation P of the residents. When a resident originally at index i is placed at final position j (positions are 1-indexed), its final happiness value is:

Final value = { h_i if (i and j have the same parity),
      −h_i if (i and j have different parities) }.

The output is the minimum number of adjacent swaps (which is equal to the inversion count of the permutation with respect to the original order) required to achieve a non-decreasing sequence of final happiness values. If no such sequence exists, output -1.

inputFormat

The first line contains an integer N (1 ≤ N ≤ 15) indicating the number of residents. The second line contains N space‐separated integers, representing the initial happiness values h₁, h₂, ..., h_N.

outputFormat

Output a single integer representing the minimum number of adjacent swaps required to make the final happiness values (after applying sign changes) non-decreasing. If it is impossible, output -1.

sample

3
1 2 3

0