Time Limit: 10 sec / Memory Limit: 256 MB
配点: 100 点
問題
次のようなゲームがある.
あるキャラクターが縦 1 列に N 個並んでいる.これらのキャラクターの色は赤,青,黄のいずれかであり,初期状態で同じ色のキャラクターが 4 つ以上連続して並んでいることはない.プレーヤーは,ある位置のキャラクターを選び他の色に変更することができる.この操作により同じ色のキャラクターが 4 つ以上連続して並ぶとそれらのキャラクターは消滅する.キャラクターが消滅することにより新たに同じ色のキャラクターが 4 つ以上連続して並ぶとそれらのキャラクターも消滅し,同じ色のキャラクターが4つ以上連続して並んでいる箇所がなくなるまでこの連鎖は続く.このゲームの目的は,消滅しないで残っているキャラクター数をなるべく少なくすることである.
例えば,下図の左端の状態で,上から 6 番目のキャラクターの色を黄色から青に変更すると,青のキャラクターが 5 つ連続するので消滅し,最終的に 3 つのキャラクターが消滅せずに残る.
初期状態における N 個のキャラクターの色の並びが与えられたとき,1 箇所だけキャラクターの色を変更した場合の,消滅しないで残っているキャラクター数の最小値 M を求めるプログラムを作成せよ.
入力
1 行目はキャラクター数 N (1 \leqq N \leqq 10\,000) だけからなる.続く N 行には 1, 2, 3 のいずれか 1 つの整数が書かれており,i + 1 行目 (1 \leqq i \leqq N) は初期状態における上から i 番目のキャラクターの色を表す(1 は赤を,2 は青を,3 は黄を表す).
出力
消滅しないで残っているキャラクター数の最小値 M を出力せよ.
入力例 1
12 3 2 1 1 2 3 2 2 2 1 1 3
出力例 1
3
入力例 2
12 3 2 1 1 2 3 2 1 3 2 1 3
出力例 2
12