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.
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.
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 the minimum number of operations in a line. If the numbers cannot be sorted in decreasing order, output -1.
6 2 3 4 1 6 5
3
4 2 3 4 1
-1