Tại Vương quốc VibeKode, kho trung tâm đưa ~N~ sản phẩm lên một dây chuyền theo thứ tự từ ~1~ đến ~N~. Sản phẩm thứ ~i~ mang mã truy xuất nội bộ ~A_i~. Đây là mã cục bộ nên nhiều sản phẩm có thể mang cùng một mã.

Đức vua yêu cầu chia dãy sản phẩm thành đúng ~K~ lô liên tiếp không rỗng. Thứ tự các sản phẩm phải được giữ nguyên và mỗi sản phẩm thuộc đúng một lô.

Trong mỗi lô, hệ thống chỉ phân biệt các sản phẩm qua mã truy xuất. Một sản phẩm được gọi là truy xuất được nếu mã của nó xuất hiện đúng một lần trong lô chứa nó. Nếu một mã xuất hiện từ hai lần trở lên trong cùng một lô thì không sản phẩm nào mang mã đó trong lô được truy xuất.

Hãy chia dãy thành ~K~ lô sao cho tổng số sản phẩm truy xuất được là lớn nhất. Các lần xuất hiện của cùng một mã trong những lô khác nhau được xét độc lập.

Dữ liệu vào

Vào từ file văn bản LOTTRACE.INP gồm:

• Dòng đầu tiên chứa hai số nguyên ~N, K~ (~1 \leq K \leq N \leq 2 \cdot 10^5~, ~N \cdot K \leq 10^6~).
• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, \ldots, A_N~ (~1 \leq A_i \leq 10^9~).

Dữ liệu ra

Ghi ra file văn bản LOTTRACE.OUT kết quả theo yêu cầu sau:

• In ra số sản phẩm truy xuất được lớn nhất có thể đạt được.

Ví dụ 1

Input

5 2
1 2 1 3 2

Output

5

Giải thích

Chia dãy thành hai lô ~[1, 2]~ và ~[1, 3, 2]~. Trong mỗi lô, mọi mã đều xuất hiện đúng một lần nên cả ~5~ sản phẩm đều truy xuất được.

Ràng buộc

• Subtask 1 (20%): ~K = 1~.
• Subtask 2 (20%): ~K = 2~.
• Subtask 3 (25%): ~N \leq 1000~, ~K \leq 10~.
• Subtask 4 (35%): Không có ràng buộc nào thêm.