题目描述

有 $n$ 头奶牛，每头那牛都有一个标号 $p_i$，现在 FJ 要把这些奶牛分成若干段，定义每段的不和谐度为：若这段里有 $k$ 个不同的数，该段的不和谐度即为 $k^2$，总的不和谐度就是所有段的不和谐度的总和。请你计算分段之后的最小不和谐度。

输入格式

• 第一行：两个整数 $n,m$。

• 第 $2\sim n+1$ 行：$n$ 个整数，代表每个奶牛的编号。

输出格式

• 第一行：一个整数，代表最小不和谐度

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

11

数据规模与约定

对于 $100\%$ 的数据，$1 \le p_i \le m \le n \le 40000$。

题目来源

Usaco2009 Mar Gold