Phân lô tài nguyên

Một khu mỏ có $N$ khu vực khai thác xếp thành một hàng ngang. Khu vực thứ $i$ chứa loại tài nguyên được mã hóa bởi số nguyên $A_i$. Khi nhiều khu vực cùng loại nằm trong một phân khu, công tác quản lý phát sinh thêm chi phí.

Yêu cầu: Cần chia toàn bộ dãy thành đúng $P$ phân khu liên tiếp nhau, mỗi phân khu phải chứa ít nhất một khu vực. Nếu trong một phân khu có $c$ khu vực cùng chứa một loại tài nguyên nào đó thì loại tài nguyên ấy đóng góp $c(c-1)/2$ vào chi phí của phân khu. Hãy tìm tổng chi phí nhỏ nhất có thể đạt được.

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên $N$ và $P$.
• Dòng thứ hai chứa $N$ số nguyên; số thứ $i$ là giá trị $A_i$ của khu vực thứ $i$.

Dữ liệu ra

Một số nguyên duy nhất là chi phí nhỏ nhất có thể đạt được.

Ràng buộc

• $1\le N\le 50000$.
• $1\le P\le min(20,N)$.
• $1\le A_i\le N$.

Subtasks

• Subtask 1 ($15\%$ số điểm): $N\le 100$, $P\le 10$.
• Subtask 2 ($15\%$ số điểm): $N\le 1000$.
• Subtask 3 ($20\%$ số điểm): Mảng $A$ chỉ chứa các giá trị $1$ hoặc $2$.
• Subtask 4 ($20\%$ số điểm): $P=2$.
• Subtask 5 ($30\%$ số điểm): Không có ràng buộc gì thêm.

Ví dụ