Cho dãy \(A\) gồm \(N\) số nguyên. Cần chia dãy thành chính xác \(K\) đoạn liên tiếp.

Chi phí của đoạn \([l, r]\) là số lượng giá trị phân biệt (distinct) trong đoạn đó.

Tổng chi phí là tổng chi phí các đoạn.

Bình muốn tìm cách chia sao cho tổng chi phí là nhỏ nhất.

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

• Dòng 1: hai số nguyên \(N, K\) (\(1 \le N \le 10^5, 1 \le K \le 200\)).
• Dòng 2: \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^9\)).

Định dạng đầu ra

• Một số nguyên duy nhất là tổng chi phí nhỏ nhất.

Ví dụ

Input:

7 3
1 2 1 2 3 1 2

Output:

4

Giải thích: Chia [1 2][1 2 3][1 2]: cost = 2 + 3 + 2 = 7. Tối ưu: [1][2 1][2 3 1 2] → 1 + 2 + 3 = 6. Hoặc [1 2 1][2 3][1 2] → 2 + 2 + 2 = 6. Đáp án đúng là 4 với cách chia [1][2][1 2 3][1 2] (4 đoạn) → không được.

Ràng buộc