Problem
Bạn được đưa cho một dải giấy ca rô gồm n ô vuông màu được đánh số từ 1 đến n từ trái sang phải. Hình vuông thứ i ban đầu được tô màu c
i.
Ta nói rằng hình vuông i và j nằm trong cùng một thành phần nếu c
i = c
j và c
i = c
k cho tất cả k thỏa mãn tôi < k < j. Nói cách khác, tất cả các ô vuông trên đoạn từ i đến j phải có cùng màu.
Ví dụ: dải [3,3,3] có 1 thành phần được kết nối, trong khi [5,2,4,4] có 3.
Điền vào trò chơi được phát trên dải này như sau:
Khi bắt đầu trò chơi, bạn chọn một ô xuất phát ngẫu nhiên (không được tính là một lượt).
Sau đó, trong mỗi lần di chuyển, bạn thay đổi màu của thành phần được kết nối có chứa hình vuông bắt đầu thành bất kỳ màu nào khác.
Tìm số lần di chuyển tối thiểu cần thiết để đổi màu toàn bộ dải thành một màu.
Đầu vào:
Dòng đầu tiên chứa một số nguyên n (1 ≤ n ≤ 5000) — số ô vuông.
Dòng thứ hai chứa các số nguyên c
1,c
2,…,c
n (1 ≤ c
i <5000) — màu ban đầu của hình vuông.
Đầu ra:
In một số nguyên duy nhất — số lần di chuyển tối thiểu để thực hiện.
Ví dụ:
| Đầu vào |
Đầu ra |
4
5 2 2 1
| 2 |
8
4 5 2 2 1 3 5 5
| 4 |
1
4 |
0 |
Giải thích:
Một trong những cách tối ưu trong ví dụ đầu tiên: [5, 2, 2, 1] -> [5, 2, 2, 2] -> [5, 5, 5, 5]