题目描述

对于一个序列，若存在一组 $(i,j)$ 使得 $i\neq j$ 且 $a_i=a_j$，我们称这两个数字之间产生了一次冲突。

现给定一个序列 $a_1,a_2,\cdots,a_n$，请将它分割为 $k$ 段，使得每一段内部的冲突次数之和最小。

输入格式

第一行：两个整数 $n$ 和 $k$，表示序列长度与需要分的段数 第二行：$n$ 个整数分别表示 $a_1,a_2,\dots,a_n$

输出格式

输出分段后，最少的冲突次数之和

5 2
3 5 3 1 4

0

样例解释 1

序列分为[3 5] [3 1 4]，没有冲突

10 2
2 3 2 3 2 3 2 3 2 3

8

样例解释 2

序列分为[2 3 2 3 2] , [3 2 3 2 3] ，两段内部冲突数均为4

数据范围

• 对于 $30\%$ 的数据，$1 \leq k \leq n \leq 1000$
• 对于 $60\%$ 的数据，$1 \leq k \leq n \leq 10000$
• 对于 $100\%$ 的数据，$1 \leq n\leq 10^5$，$k\leq 20$，$1\le a_i\le n$