漫长的小纸带

[The English statement for T4](https://www.luogu.com.cn/problem/U508235) 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 $ | - | $ 8 $ | | $ 3 $ | $ 2000 $ | - | $ 16 $ | | $ 4 $ | - | A | $ 16 $ | | $ 5 $ | - | B | $ 24 $ | | $ 6 $ | - | - | $ 28 $ | 特殊性质 A：所有的 $ a_i $ 在 $ [1,10^9] $ 内等概率随机生成，且本子任务只有 $ 1 $ 个测试点。 特殊性质 B：$ 1 \le a_i \le 1000 $。