题目描述

给定一个包含 $n$ 个整数的数组 $a_{1}...\ a_{n}$ 。一个子段的代价定义为：该子段内由不同下标组成、且对应元素相等的无序下标对数量。请将给定数组划分为 $k$ 个互不相交的非空子段，使得这些子段的代价之和尽可能小。每个元素都必须恰好属于一个子段。

输入格式

第一行包含两个整数 $n$ 和 $k$（ $2 \le n \le 10^{5}$ ， $2 \le k \le \min(n,20))$ ）——数组的长度以及需要划分出的子段数量。

下一行包含 $n$ 个整数 $a_{1},a_{2},...,a_{n}$（ $1 \le a_{i} \le n$ ）——数组中的元素。

输出格式

输出一个整数：划分后所有子段的最小可能总代价。

7 3
1 1 3 3 3 2 1

1

10 2
1 2 1 2 1 2 1 2 1 2

8

13 3
1 2 2 2 1 2 1 1 1 2 2 1 1

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$ 。