Một siêu thị có dãy ~n~ gian hàng liên tiếp nhau. Gian hàng thứ ~i~ chuyên bán sản phẩm loại ~a_i~. Cần chia toàn bộ dãy gian hàng thành đúng ~k~ phân khu liên tiếp nhau, mỗi phân khu phải chứa ít nhất một gian hàng. Trong một phân khu có thể bán nhiều loại sản phẩm. Nếu có hơn một gian hàng cùng loại sản phẩm trong một phân khu thì cần thuê người quản lý. Một phân khu có ~c~ gian hàng cùng bán một loại sản phẩm, thì chi phí thuê người quản lý loại sản phẩm đó là ~c(c-1)/2~. Chi phí thuê quản lý của một phân khu bằng tổng chi phí thuê quản lý từng loại sản phẩm của phân khu đó. Chi phí thuê quản lý của siêu thị bằng tổng chi phí thuê quản lý của tất cả các phân khu.

Yêu cầu: Hãy tìm cách chia các phân khu sao cho chi phí thuê quản lý của siêu thị là nhỏ nhất.

Input

• Dòng thứ nhất: hai số nguyên ~n~ và ~k~ ~(1 \le n \le 5 \cdot 10^4; 1 \le k \le \min(20, n))~;

• Dòng thứ hai: ~n~ số nguyên ~a_1, \dots, a_n~ ~(1 \le i \le n; 1 \le a_i \le n)~.

Output

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

Scoring

Sample Input 1

9 2
1 3 1 3 1 3 1 3 1

Sample Output 1

6

Notes

Một cách chia ~2~ phân khu tối ưu là ~[1, 3, 1, 3]~ và ~[1, 3, 1, 3, 1]~. Phân khu thứ nhất có hai gian hàng cùng bán loại sản phẩm ~1~ và hai gian hàng bán loại sản phẩm ~3~ nên tốn chi phí là ~2(2-1)/2 + 2(2-1)/2 = 2~; phân khu thứ hai có ba gian hàng cùng bán loại sản phẩm ~1~ và hai gian hàng bán loại sản phẩm ~3~ nên tốn chi phí là ~2(2-1)/2 + 3(3-1)/2 = 4~. Tổng chi phí ~2~ phân khu là ~2+4=6~.