题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$。我们可以将它分割成任意多段，每一段可以有任意多个数字。

定义每一段数字的冲突值，为 $k^2$，其中 $k$ 为这一段数字的种类数量。

请问，该如何分段，才能使该数列的冲突值之和最小？

输入格式

输入共两行 第一行，一个正整数$n$ 第二行，$n$个正整数，分别表示$a_1,a_2,...,a_n$

输出格式

输出共一行，一个正整数表示数列最小权重值

10
1 2 1 1 2 1 3 4 2 2

7

样例解释 1

{1,2,1,1,2,1},{3},{4},{2,2} 按此分法： 第一段权重为22=4 后面三段权重为11=1

数据范围

• 对于 $30\%$ 的数据，$n\leq 100$
• 对于 $60\%$ 的数据，$n\leq 5000$
• 对于 $100\%$ 的数据，$1\leq n\leq 50,000$
• $1\leq a_i\leq n$