레이팅 미적용설명
次のようなゲームがある.
あるキャラクターが縦 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
입력
12
3
2
1
1
2
3
2
2
2
1
1
3출력
3문제 정보