子段划分

• 时间限制：1 秒
• 内存限制：512 MiB

题目描述

给定一个长度为 $n$ 的正整数序列 $a$，需要将该序列划分成恰好 $k$ 个连续非空子段。

一个子段的费用等于其中数值相同的元素对数。具体地，若数值 $x$ 在该子段中出现 $c$ 次，则它对费用的贡献为 $\frac{c(c-1)}{2}$；子段总费用为所有不同数值贡献之和。

请最小化这 $k$ 个子段的费用之和，并输出最小值。

输入格式

第一行包含两个整数 $n,k$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个整数，表示最小费用和。

样例输入 1

8 2
2 3 2 8 1 2 3 1

样例输出 1

1

样例输入 2

15 3
1 2 3 2 1 2 1 2 2 1 2 3 1 2 1

样例输出 2

8

样例输入 3

20 4
1 2 3 9 8 2 7 1 2 3 3 2 8 9 1 2 3 3 2 1

样例输出 3

3

数据范围

对于所有测试数据，保证 $2 \le n \le 10^5$，$2 \le k \le \min(n,20)$，$1 \le a_i \le n$。