CF868F.Yet Another Minimization Problem

You are given an array of n integers _a_1... a__n. The cost of a subsegment is the number of unordered pairs of distinct indices within the subsegment that contain equal elements. Split the given array into k non-intersecting non-empty subsegments so that the sum of their costs is minimum possible. Each element should be present in exactly one subsegment.

给你一个包含 $n$ 个整数的数组 $a_1, \dots, a_n$。一个子区间的代价定义为：该子区间内所有满足元素值相等的不同下标对（无序）的个数。请将给定数组划分为 $k$ 个互不相交、非空的子区间，使得这些子区间的代价之和最小。每个元素必须且仅属于其中一个子区间。

The first line contains two integers n and k (2 ≤ n ≤ 105, 2 ≤ k ≤ min (n, 20)) — the length of the array and the number of segments you need to split the array into.

The next line contains n integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ n) — the elements of the array.

第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 10^5$，$2 \leq k \leq \min(n, 20)$）—— 分别表示数组的长度以及需要将数组划分成的段数。

下一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq n$）—— 表示数组的元素。

Print single integer: the minimum possible total cost of resulting subsegments.

输出一个整数：最终子段的最小可能总成本。

In the first example it's optimal to split the sequence into the following three subsegments: [1], [1, 3], [3, 3, 2, 1]. The costs are 0, 0 and 1, thus the answer is 1.

In the second example it's optimal to split the sequence in two equal halves. The cost for each half is 4.

In the third example it's optimal to split the sequence in the following way: [1, 2, 2, 2, 1], [2, 1, 1, 1, 2], [2, 1, 1]. The costs are 4, 4, 1.

在第一个例子中，将序列最优地划分为以下三个子段：[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。