시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 3 2 2 66.667%

문제

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

あるキャラクターが縦 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

예제 출력

3

힌트