問題文

Wさんの住む部屋には $N$ 個のぬいぐるみが一列に並んでいます。

ぬいぐるみには 肉食動物・草食動物・鳥 の $3$ つの種類があります。

最初のぬいぐるみ列の状態は、長さ $N$ の数列 $A$ で表されます。

$A_i$ が $0,1,2$ の時はそれぞれ、ぬいぐるみ列の左から $i$ 番目のぬいぐるみが 肉食動物、草食動物、鳥 であることを表しています。

Wさんは、以下の条件を満たすぬいぐるみの列を安全なぬいぐるみ列と呼びます。

• 全ての肉食動物と草食動物のペアに関して、隣り合っていない。

Wさんは以下の操作を $0$ 回以上の任意の回数繰り返して、ぬいぐるみ列を安全なぬいぐるみ列にしたいです。

• 肉食動物と草食動物を $1$ つずつ選び、場所を入れ替える。

Wさんが安全なぬいぐるみ列にできるかを判定し、可能な場合は必要な操作の最小回数を求めてください。

入力

$N$
$A_1\ A_2\ ... A_N$

• 入力は全て整数
• $2 \le N \le 5000$
• $0 \le A_i \le 2$
• $A_i$ が $0,1,2$ の時はそれぞれ、ぬいぐるみ列の左から $i$ 番目のぬいぐるみが 肉食動物、草食動物、鳥 であることを表す。

出力

何回操作しても安全なぬいぐるみ列にできない場合、 $-1$ を出力してください。

そうでない場合、安全なぬいぐるみ列にするのに必要な最小の操作回数を出力してください。

最後に改行してください。

サンプル

3
2 0 1

-1

5
0 0 2 2 0

0

15
0 0 1 2 0 1 0 2 0 1 1 2 1 0 1

2