该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

$N$ 个不超过 $M$ 的整数构成一个数列 $A_1, A_2, ……, A_N$，现在要将其划分成若干段。对于每一段，如果其中含有的不同整数有 $x$ 个，则该段的代价为 $x^2$。

划分的总代价为每一段的代价之和。

问：如何划分可以使得总代价最小？你只需要输出这个最小值。

输入格式

第一行：两个整数 N, M

接下来 N 行，每行一个整数，依次表示 $A_1, A_2, ……, A_N$

输出格式

一个整数，表示划分的最小总代价

样例输入

10 3 
1
2
3
1
1
2
3
2
3
2

样例输出

8

样例解释

可以这样划分：1 / 2 / 3 / 1 1 / 2 3 2 3 2

总代价为 1 + 1 + 1 + 1 + 4 = 8

数据范围

$1 ≤ N ≤ 50000, 1 ≤ M ≤ N, 1 ≤ Ai ≤ M$