A93904.Alice 的分段游戏

给定一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$（元素为正整数）。你需要把它划分成恰好 $k$ 个连续非空段，设第 $t$ 段为区间 $[L_t,R_t]$，并定义一段的代价为：

$$\mathrm{cost}(L,R)=\sum_{x}\binom{\#\{\, i\in[L,R]\mid a_i=x \,\}}{2}.$$

也就是说，在同一段中，每个数的出现次数为 $c$ 就会贡献 $\binom{c}{2}$ 的代价。请最小化 $k$ 段代价之和：

$$\min \sum_{t=1}^{k}\mathrm{cost}(L_t,R_t),$$

并输出该最小值。

• 第一行两个整数 $n,k$。
• 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

输出一个整数，表示最小总代价。

数据范围

• $1\le n\le 2\times 10^5$；
• $1\le k\le \min(n,20)$；
• $1\le a_i\le 2\times 10^5$；
• 答案不超过 $2^{63}-1$（使用 64 位有符号整数即可）。

测试点与数据范围

测试点	规模约束
$1\sim 6$	$n\le 2\times 10^4,\ k\le 10$
$7\sim 20$	$n\le 2\times 10^5,\ k\le 20$

样例解释

• 样例一 : 解释：一种最优分法是 $[1,2,1]\ |\ [2,1]$。第一段中 $1$ 出现 $1$ 次贡献 $1$，第二段中没有重复对，总代价为 $1$。

• 样例二： 解释：可分为 $[1,1]\ |\ [1,2]\ |\ [2,3]$，总代价 $1$。