题目描述
给定一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$。我们可以将它分割成任意多段，每一段可以有任意多个数字。
定义每一段数字的冲突值，为 $k^2$，其中 $k$ 为这一段数字的种类数量。
请问，该如何分段，才能使该数列的冲突值之和最小？
输入
输入共两行
第一行，一个正整数$n$
第二行，$n$个正整数，分别表示$a_1,a_2,...,a_n$
输出
输出共一行，一个正整数表示数列最小权重值
样例输入输出
输入#1
复制
10
1 2 1 1 2 1 3 4 2 2
提示
+ 对于 $30\%$ 的数据，$n\leq 100$
+ 对于 $60\%$ 的数据，$n\leq 5000$
+ 对于 $100\%$ 的数据，$1\leq n\leq 50,000$
+ $1\leq a_i\leq n$
样例1说明:{1,2,1,1,2,1},{3},{4},{2,2}
按此分法：
第一段权重为2*2=4
后面三段权重为1*1=1