Đa dạng

Một công ty khai thác khoáng sản sở hữu một dãy \(n\) khu vực, được đánh số từ \(1\) đến \(n\). Mỗi khu vực thứ \(i\) có một loại khoáng sản được đặc trưng bởi mã số \(a_i\). Ban giám đốc muốn chia dãy khu vực này thành \(k\) đoạn liên tiếp không trống để giao cho \(k\) đội khai thác.

Mức độ "đa dạng" của một đoạn khu vực được định nghĩa là số lượng cặp khu vực có cùng loại khoáng sản trong đoạn đó. Mục tiêu là tìm cách chia để tổng mức độ "đa dạng" của tất cả \(k\) đoạn là nhỏ nhất.

Input

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

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) (\(2 \le n \le 10^5\), \(2 \le k \le \min(n, 20)\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le n\)), là mã số loại khoáng sản tại mỗi khu vực.

Output

In ra một số nguyên duy nhất là tổng mức độ đa dạng tối thiểu.

Example

9 3
1 2 2 3 2 1 1 2 3

1

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 2000\).
• Subtask \(4\) (\(25\%\) số điểm) : không có ràng buộc nào thêm.