题目背景

The English statement for T4

You can also see the pdf at the bottom of the chinese problem statement.

小 $\zeta$ 是一个喜欢打暴力的 OIer。在每次模拟赛中，他秉持着“10 分钟想不出来正解那就把暴力糊上去”的理念，每次都稳定地拿到很高的分数；平时训练时，他会关注题目的部分分，针对部分分任务进行求解，有时在部分分求解上使用的时间比这个题正解的思考都长。

题目描述

小 $\zeta$ 经过了几年的暴力训练，暴力水平更是炉火纯青。在 S-PSC 2077 的比赛中，他惊喜的发现第二题《漫长的小纸带》是一道很困难的题目，正适合他这种暴力选手发挥。

这道题目是多测题目，在某个测试点内有 $n$ 组数据，第 $i$ 组数据的规模为 $a_i$。他写出了一个暴力程序，对于一段连续的数据，程序解决这段数据需要消耗的时间为这段数据中出现的不同的 $a_i$ 的种类数平方。形式化地讲，对于一个从第 $l$ 组到第 $r$ 组的连续的数据段，记 $S=\{a_i|l \le i \le r\}$，程序需要消耗 $|S|^2$ 的时间来一起解决它们。

现在，他给你 $n$ 和 $n$ 组数据的规模，请找到一种将这些数据划分成若干个数据段的方案，使得程序消耗的总时间最短。

输入格式

第一行一个整数 $n$。

接下来一行 $n$ 个整数 $a_i$，代表每一组测试数据的规模。

输出格式

输出一个数代表总时间消耗。

5
1 2 3 4 5

5

6
1 2 2 1 2 3

5

9
1 2 1 4 1 2 1 1 2

8

21
1 2 1 2 1 2 1 2 1 2 3 4 5 6 7 1 2 1 2 1 2

13

提示

【样例 3 解释】

分段方式为：

• 第一段 $\{1\}$，消耗为 $1$。
• 第二段 $\{2\}$，消耗为 $1$。
• 第三段 $\{1\}$，消耗为 $1$。
• 第四段 $\{4\}$，消耗为 $1$。
• 第五段 $\{1,2,1,1,2\}$，消耗为 $4$。

故程序总共消耗的时间为 $8$。

【数据范围】

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5$，$1 \le a_i \le 10^9$。

提示：本题开启捆绑测试。

子任务编号	$n \le$	特殊性质	分数
$1$	$10$	-	$8$
$2$	$300$
$3$	$2000$		$16$
$4$	-	A
$5$		B	$24$
$6$		-	$28$

特殊性质 A：所有的 $a_i$ 在 $[1,10^9]$ 内等概率随机生成，且本子任务只有 $1$ 个测试点。

特殊性质 B：$1 \le a_i \le 1000$。