Chia kẹo

Trong một lớp học, hôm nay là ngày sinh nhật của \(m\) bạn. Để chúc mừng, cả lớp đã mua \(n\) gói kẹo. Mỗi gói kẹo có một loại kẹo riêng, được đánh số bằng một số nguyên dương từ \(1\) đến \(n\). Lớp trưởng đã sắp xếp các gói kẹo thành một dãy, đánh số từ \(1\) đến \(n\).

Để chia kẹo cho \(m\) bạn, lớp trưởng quyết định chia dãy kẹo này thành \(m\) đoạn liên tiếp không rỗng. Mỗi bạn sẽ nhận một đoạn kẹo. Vì các bạn đều thích kẹo có nhiều loại khác nhau, giá trị của mỗi đoạn kẹo được tính bằng số lượng các loại kẹo khác nhau có trong đoạn đó.

Lớp trưởng muốn làm hài lòng tất cả các bạn và thể hiện sự khéo léo của mình bằng cách tìm cách chia dãy kẹo thành \(m\) đoạn sao cho tổng giá trị của tất cả \(m\) đoạn là lớn nhất có thể.

Input

Dữ liệu vào được cung cấp từ đầu vào chuẩn (stdin) theo định dạng sau:

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(m\) (\(1 \le n \le 50000\), \(1 \le m \le \min(n, 50)\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le n\)), là loại kẹo của gói kẹo thứ \(i\).

Output

In ra một số nguyên duy nhất là giá trị lớn nhất của tổng giá trị các đoạn.

Example

8 3
7 7 8 7 7 8 1 7

6

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \leq 20\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \leq 200\).
• Subtask \(3\) (\(25\%\) số điểm): \(n \leq 1000\).
• Subtask \(4\) (\(25\%\) số điểm): không có ràng buộc gì thêm.