Mot hang rao gom \(N\) cot, cot i co mau sac c_i (1..\(N\)). Ban can son lai hang rao bang dung \(K\) mau moi, moi mau phu mot doan lien tiep. Chi phi cua mot doan \([l,r]\) la so luong mau sac khac nhau co trong doan do. Hay chon cach chia hang rao thanh \(K\) doan lien tiep sao cho tong chi phi nho nhat.\ \ Input:

• Dong dau: \(N\), K (\(1 \le K \le N \le 10^5, K \le 200\))
• Dong sau: \(c_1..c_N\) (\(1 \le c_i \le N\))

Output: Tong chi phi nho nhat.\ \ Vi du: Input:

6 3
1 2 1 3 2 1

Output:

4

Giai thich: Chia \([1,3]\) (\(mau 1, 2, 1: cost=2\)), \([4,4]\) (\(mau 3: cost=1\)), \([5,6]\) (\(mau 2, 1: cost=2\)), tong = 5. Phương án tối ưu: \([1,2]\) (2) + \([3,4]\) (2) + \([5,6]\) (2) = 6. Đáp số tối ưu là 4.

#

Định dạng đầu vào

• Dòng 1: Hai số nguyên \(N\) và K (\(1 \le K \le N \le 3000\)).
• Dòng 2: \(N\) số nguyên \(c_1, c_2, \dots, c_N\) (\(1 \le c_i \le N\)).

Định dạng đầu ra

• In ra tổng số lượng màu sắc khác nhau nhỏ nhất.

Ví dụ

Input:

6 2
1 1 2 2 3 3

Output:

3

Giải thích: Đoạn 1 gồm [1, 1, 2] (2 màu), đoạn 2 gồm [2, 3, 3] (2 màu) -> hoặc chia [1,1,2,2] (2 màu) và [3,3] (1 màu) -> tổng 3 màu.

Ràng buộc & Subtasks