問題一覧 > 通常問題

No.1606 Stuffed Animals Keeper

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 84
作問者 : SPD_9X2SPD_9X2 / テスター : tute7627tute7627 penguinmanpenguinman
5 ProblemId : 6315 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-14 17:29:59

問題文

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$ を出力してください。

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

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

サンプル

サンプル1
入力
3
2 0 1
出力
-1

どのように操作しても安全なぬいぐるみ列にできません。

サンプル2
入力
5
0 0 2 2 0
出力
0

草食動物がいないので最初から安全なぬいぐるみ列です。

サンプル3
入力
15
0 0 1 2 0 1 0 2 0 1 1 2 1 0 1
出力
2

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。