第８回日本情報オリンピック　予選３

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 を出力せよ．

入出力例

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
   

3
   

12
   

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

テストデータ