Robot Arm

PCK Industry is developing a new robot arm. The task of this robot arm is to sort $N$ parts assigned numbers from 1 to $N$ in a single row, in order of decreasing number.

The robot arm can select three parts in one operation (they do not have to be next to each other) and perform the following exchange operations on them.

• When the selected parts are numbered a, b, and c from the beginning, swap the positions of these parts in the order b, c, a or c, a, b.

For example, if the parts are lined up as 3 6 1 5 4 2 and the robot arm selects the part with 6 5 4, these positions can be swapped and rearranged in the order 3 5 1 4 6 2 or 3 4 1 6 5 2.

Write a program which reads a sequence of parts and finds the minimum number of operations of the robot arm required to sort them in the order of decreasing number. If it is not possible to sort the parts in decreasing order no matter how the operations are performed, output -1.

Input

The input is given in the following format.

$N$
$h_1$ $h_2$ ... $h_N$

The first line gives the number of parts $N$ ($3 \leq N \leq 200,000$). The second line gives the number of each part $h_i$ ($1 \leq h_i \leq N$). All numbers are different (if $i \ne j$, then $h_i \ne h_j$)

Output

Output the minimum number of operations in a line. If the numbers cannot be sorted in decreasing order, output -1.

Sample Input and Output

Sample Input 1

6
2 3 4 1 6 5

Sample Output 1

3

Sample Input 2

4
2 3 4 1

Sample Output 2

-1

 

---