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.

Input

• 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~.

Output

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

Scoring

Dữ liệu đảm bảo:

• ~1 \le N \le 50000~.

• ~1 \le P \le \min(20, N)~.

• ~1 \le A_i \le N~.

Sample Input 1

7 3
2 5 2 5 2 5 2

Sample Output 1

1

Notes

Một cách chia tối ưu là ~[2, 5] \mid [2, 5] \mid [2, 5, 2]~.

Phân khu thứ nhất có chi phí ~0~ vì không có cặp tài nguyên nào trùng nhau. Phân khu thứ hai cũng có chi phí ~0~. Phân khu thứ ba có hai khu vực cùng chứa tài nguyên ~2~ nên đóng góp đúng ~1~ cặp trùng nhau. Tổng chi phí là ~0 + 0 + 1 = 1~.