009 - ロボットアーム

問題文

PCK工業では、新作のロボットアームを開発しています。このロボットアームの仕事は、$1$列に並んだ $1$ から $N$ の番号が割り振られた $N$ 個の部品を、番号が小さい順に並べ替えることです。 ロボットアームは $1$回の動作で$3$つの部品を選択し（隣り合っている必要はありません）、それらに対して以下の交換作業を行うことができます。

• 選んだ部品の番号が先頭から $a,\ b,\ c$ のとき、これらの部品の位置を $b,\ c,\ a$ または $c,\ a,\ b$

の順番に入れ替える たとえば、部品が $3\ 6\ 1\ 5\ 4\ 2$ と並んでいて、ロボットアームが $6\ 5\ 4$ の部品を選択した場合は、これらの位置を交換して $3\ 5\ 1\ 4\ 6\ 2$ または $3\ 4\ 1\ 6\ 5\ 2$ の順番に並べ替えることができます。

課題

部品の列が与えられる。これらを番号が小さい順に並べ替えるために必要な、ロボットアームの最小の操作回数を求めるプログラムを作成せよ。
ただし、どのように操作を行っても番号が小さい順にできない場合は$-1$ を出力せよ。

入力

入力は以下の形式で与えられる。

$N$
$h_{1} \  h2_{2} \  \cdots \  h_{N}$

$1$行目に部品の数$N \ (3 \leq N \leq 200,000)$が与えられる。$2$行目に各部品の番号$h_{i} \ (1 \leq h_{i} \leq N)$が与えられる。
ただし、すべての番号は異なる$(i \neq j$ならば$h_{i} \neq h_{j})$

出力

最小の操作回数を$1$行に出力する。ただし、番号が小さい順に並べ替えることができない場合は $-1$ を$1$行に出力する。

入出力例

入力例1

6
2 3 4 1 6 5

出力例1

3

---

入力例2

4
2 3 4 1

出力例2

-1

---