문제
다음과 같은 게임이 있다. 어떤 캐릭터가 세로로 \(N\)개 한 줄로 서 있다. 각 캐릭터의 색은 빨강, 파랑, 노랑 중 하나이고, 처음에는 같은 색이 4개 이상 연속해 있지 않다. 플레이어는 한 위치의 캐릭터를 골라 다른 색으로 바꿀 수 있다. 이 조작으로 같은 색이 4개 이상 연속하면 그 캐릭터들은 사라진다. 사라진 뒤 다시 같은 색이 4개 이상 연속하면 그것들도 사라지고, 같은 색이 4개 이상 연속한 곳이 없어질 때까지 연쇄가 이어진다. 목표는 사라지지 않고 남는 캐릭터 수를 되도록 적게 하는 것이다. 예를 들어 위에서부터 6번째 캐릭터의 색을 노랑에서 파랑으로 바꾸면 파랑이 5개 연속하여 사라지고, 결국 3개가 남는다. 처음 상태의 색 배치가 주어질 때, 한 곳만 색을 바꾼 경우 남게 되는 캐릭터 수의 최솟값 \(M\)을 구하는 프로그램을 작성하라. |
입력
입력은 다음 형식으로 주어진다.
\(N\)
\(C_1\)
\(C_2\)
\(\vdots\)
\(C_N\)
- 첫째 줄에 캐릭터 수 \(N\)이 주어진다.
- 다음 \(N\)줄에 \(1\), \(2\), \(3\) 중 하나의 정수가 한 줄에 하나씩 주어진다. \(i+1\)번째 줄은 위에서부터 \(i\)번째 캐릭터의 색이다. \(1\)은 빨강, \(2\)는 파랑, \(3\)은 노랑이다.
- \(1 \le N \le 10000\)
- 입력되는 값은 모두 정수이다.
출력
다음 형식으로 출력한다.
첫째 줄에 남게 되는 캐릭터 수의 최솟값 \(M\)을 출력한다.
예시 1
입력
12
3
2
1
1
2
3
2
2
2
1
1
3
출력
3
설명
위에서부터 6번째 캐릭터를 노랑에서 파랑으로 바꾸면 파랑이 연속하여 사라지고, 3개가 남는다.
예시 2
입력
12
3
2
1
1
2
3
2
1
3
2
1
3
출력
12
설명
어느 한 곳의 색을 바꿔도 4개 이상이 연속하지 않아 모두 남는다.