Có \(N\) nhân vật xếp thành một cột từ trên xuống dưới. Mỗi nhân vật có một trong ba màu: đỏ, xanh lam hoặc vàng. Ban đầu, không có từ bốn nhân vật cùng màu trở lên đứng liên tiếp.

Người chơi chọn đúng một nhân vật và đổi màu của nhân vật đó thành một trong hai màu còn lại. Nếu thao tác này tạo ra một nhóm gồm ít nhất bốn nhân vật cùng màu liên tiếp, toàn bộ nhóm đó biến mất. Các nhân vật còn lại khép lại chỗ trống và giữ nguyên thứ tự tương đối. Nếu khi đó lại xuất hiện một nhóm gồm ít nhất bốn nhân vật cùng màu liên tiếp, nhóm này cũng biến mất. Phản ứng dây chuyền tiếp tục cho đến khi không còn nhóm nào như vậy.

Mục tiêu của trò chơi là làm cho số nhân vật còn lại nhỏ nhất có thể.

Yêu cầu

Cho màu của \(N\) nhân vật theo thứ tự ban đầu. Hãy tìm số nhân vật còn lại nhỏ nhất \(M\) sau khi đổi màu đúng một nhân vật và để phản ứng dây chuyền kết thúc.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa số nguyên \(N\).
• \(N\) dòng tiếp theo, mỗi dòng chứa một số nguyên thuộc \(\{1,2,3\}\). Dòng thứ \(i+1\) biểu diễn màu của nhân vật thứ \(i\) từ trên xuống dưới: \(1\) là đỏ, \(2\) là xanh lam, \(3\) là vàng.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên \(M\), là số nhân vật còn lại nhỏ nhất.

Ràng buộc

• \(1\le N\le10\,000\).
• Mỗi màu được biểu diễn bằng \(1\), \(2\) hoặc \(3\).
• Ban đầu không có từ bốn nhân vật cùng màu trở lên đứng liên tiếp.

Chấm điểm

Bài có \(4\) bộ dữ liệu chấm, mỗi bộ \(5\) điểm, tổng cộng \(20\) điểm.

Ví dụ

12
3
2
1
1
2
3
2
2
2
1
1
3

3

Đổi màu nhân vật thứ \(6\) từ trên xuống từ vàng thành xanh lam. Khi đó, năm nhân vật xanh lam liên tiếp biến mất. Tiếp theo, bốn nhân vật đỏ trở thành liên tiếp và cũng biến mất. Cuối cùng còn lại ba nhân vật.

12
3
2
1
1
2
3
2
1
3
2
1
3

12