Tô màu

Xem PDF

Điểm: 1900 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trên một đường thẳng cho \(n\) hình vuông xếp thành một hàng đánh số 1, 2, ..., \(n\) từ trái qua phải. Hình vuông thứ \(i\) có màu là \(c_i\).

Ta nói rằng một dãy hình vuông từ vị trí \(i\) đến vị trí \(j\) là một mảng màu nếu như \(c_i=c_j\)\(c_i=c_k\) với mọi \(i<k<j\). Nói cách khác tất các các hình vuông từ vị trí \(i\) đến vị trí \(j\) là cùng một màu.

Mỗi thao tác bạn có thể tô lại màu cho các hình vuông trong một mảng màu thành màu mới.
Hỏi rằng số thao tác ít nhất cần thực hiện để đưa tất cả \(n\) hình vuông về cùng một màu là bao nhiêu

Input

  • Dòng đầu tiên ghi số nguyên dương \(n\) (\(n\le 5000\)) - số hình vuông
  • Dòng thứ hai ghi \(n\) số nguyên dương \(c_1,c_2,…,c_n\) (\(1\le c_i\le 5000\)) - màu ban đầu của các hình vuông.

Output

  • In ra một số nguyên là số thao tác nhỏ nhất cần thực hiện

Example

Test 1

Input
4
5 2 2 1 
Output
2
Note

Trong ví dụ thứ nhất biển đổi: \([5, 2, 2, 1] \rightarrow [5, 5, 5, 1] \rightarrow [1, 1, 1, 1]\)

Test 2

Input
8
4 5 2 2 1 3 5 5 
Output
4

Bình luận

Không có bình luận nào.