ロボットアーム

PCK工業では、新作のロボットアームを開発しています。このロボットアームの仕事は、１列に並んだ1から$N$の番号が割り振られた$N$個の部品を、番号が小さい順に並べ替えることです。

ロボットアームは1回の動作で３つの部品を選択し（隣り合っている必要はありません）、それらに対して以下の交換作業を行うことができます。

• 選んだ部品の番号が先頭から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$ $h_2$ ... $h_N$

１行目に部品の数$N$ ($3 \leq N \leq 200,000$)が与えられる。２行目に各部品の番号$h_i$ ($1 \leq h_i \leq N$)が与えられる。ただし、すべての番号は異なる（$i \ne j$ならば$h_i \ne h_j$）

出力

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

入出力例

入力例１

6
2 3 4 1 6 5

出力例１

3

入力例２

4
2 3 4 1

出力例２

-1

 

---