Chain

Time Limit : 1 sec, Memory Limit : 65536 KB

連鎖

問題

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

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

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。

Notes on Submission

標準入出力を行うプログラムを作成して下さい.

上記形式で複数のデータセットが与えられます. N が 0 のときデータセットの終わりを示します.

Sample Input

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
0

Sample Output

3
12

Source: 8th Japanese Olympiad in Informatics, Preliminary Round , 2008-12-14
http://www.ioi-jp.org/