番茄炒蛋拳

题目背景

题目描述

嘉然小姐有一串长度为 $n$ 的珠子。一开始，这些珠子都没有颜色。她计划给珠子上色，让它们更迷人。

在每次操作中，嘉然会选择一些连续的珠子（一个区间），并将它们都涂上它们的目标颜色。当她给有 $k$ 种不同目标颜色的串珠涂色时，消耗为 $k^2$。

现在，嘉然希望以尽可能低的成本来实现她的理想串珠。你应该告诉她最小的成本是多少。

输入格式

有多个测试用例，第一行输入一个 $T （ T \le 10 ）$，表示测试用例组数。

对于每个测试用例，第一行包含一个整数 $n （1 \le n \le 5 \times 10^4）$ ，表示珠子的数量。

第二行包含 $a_1,a_2, \cdot \cdot \cdot ,a_n（1 \le a_i \le 10^9）$，表示每颗珠子的目标颜色。

输出格式

对于每个测试用例，输出一行一个整数表示最小的成本。

样例 #1

input #1

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

output #1

2
7

数据范围

对于 $10 \%$ 的数据，满足 $n \le 200$。

对于 $40 \%$ 的数据，满足 $n \le 6000$。

对于 $100 \%$ 的数据，满足 $n \le 50000$。

闲话

做不出来的人将被嘉然小姐的番茄炒蛋拳图图。