给定一个由 n 个整数 a1...an 组成的数组。子段的成本是子段内包含相同元素的不同索引的无序对的数量。将给定数组拆分为 k 个不相交的非空子段,以使它们的成本总和尽可能最小。每个元素应该恰好出现在一个子段中。
输入
第一行包含两个整数 n 和 k (2 ≤ n ≤ 105, 2 ≤ k ≤ min (n, 20)) — 数组的长度以及需要将数组分割成的段数。
下一行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ n) — 数组的元素。
输出
打印单个整数:结果子段的最小可能总成本。
示例
输入 #1
7 3 1 1 3 3 3 2 1
输出 #1
1
输入 #2
10 2 1 2 1 2 1 2 1 2 1 2
输出 #2
8
输入 #3
13 3 1 2 2 2 1 2 1 1 1 2 2 1 1
输出 #3
9
注意
在第一个示例中,最好将序列分为以下三个子段:[1]、[1, 3]、[3, 3, 2, 1]。成本为 0、0 和 1,因此答案为 1。
在第二个示例中,最好将序列分成相等的两半。每一半的成本是4。
在第三个示例中,最好按以下方式分割序列:[1, 2, 2, 2, 1], [2, 1, 1, 1, 2], [2, 1, 1]。成本为 4, 4, 1。