JOI logo
第8回日本情報オリンピック 予選3

2008年12月14日
情報オリンピック日本委員会

問題
   連鎖

問題

次のようなゲームがある.

あるキャラクターが縦 1 列に N 個並んでいる. これらのキャラクターの色は赤,青,黄のいずれかであり, 初期状態で同じ色のキャラクターが4つ以上連続して並んでいることはない. プレーヤーは,ある位置のキャラクターを選び他の色に変更することができる. この操作により同じ色のキャラクターが4つ以上連続して並ぶとそれらのキャラクターは消滅する. キャラクターが消滅することにより新たに同じ色のキャラクターが4つ以上連続して並ぶとそれらのキャラクターも消滅し,同じ色のキャラクターが4つ以上連続して並んでいる箇所がなくなるまでこの連鎖は続く. このゲームの目的は, 消滅しないで残っているキャラクター数をなるべく少なくすることである.

例えば, 下図の左端の状態で, 上から6番目のキャラクターの色を黄色から青に変更すると, 青のキャラクターが5つ連続するので消滅し, 最終的に3つのキャラクターが消滅せずに残る.

連鎖の例

初期状態における N 個のキャラクターの色の並びが与えられたとき, 1箇所だけキャラクターの色を変更した場合の, 消滅しないで残っているキャラクター数の最小値 M を求めるプログラムを作成せよ.

入力

1行目はキャラクター数 N (1 ≦ N ≦ 10000) だけからなる. 続く N 行には 1, 2, 3 のいずれか1つの整数が書かれており, i + 1 行目 (1 ≦ i ≦ N) は初期状態における上から i 番目のキャラクターの色を表す(1 は赤を,2 は青を,3は黄を表す).

出力

消滅しないで残っているキャラクター数の最小値 M を出力せよ.

入出力例

入力例1 入力例2
12
3
2
1
1
2
3
2
2
2
1
1
3
  
12
3
2
1
1
2
3
2
1
3
2
1
3
   
 
出力例1 出力例2
3
   
12
   

※各入出力例のデータは, 右クリック等によりファイルに保存して利用可能です.


テストデータ

入力データ 入力1 入力2 入力3 入力4 入力5