1507:数组的贡献值

时间限制: 4 S | 内存限制: 65536 KB
Accept: 29 | Submit: 58
[提交] [状态] [讨论版]
描述

罗少经常刷题,这天他又看到了一道很有意思的题目。

给定一个长度为 n 的数组,定义数组的贡献值为数组中 每个数首次出现的位置 * 每个数出现的次数 之和(相同的数字只计算一次)。

例如:1 2 2 3 1,数字 1 首次出现的位置是 1,总共出现了 2 次,所以提供 1 * 2 = 2 的贡献值,数字 2 是 2 * 2 = 4,数字 3 是 4 * 1 = 4,因此这个数组的贡献值为 2 + 4 + 4 = 10。

但很显然这样是难不倒罗少的,所以附加了一个条件,你可以任意改变数组中数的位置,问改变后数组最大的贡献值是多少?

输入

第一行是一个正整数 T 代表测试案例的数量。(1 <= T <= 10)

每组案例包含一个正整数 n ,代表数组的长度。(1 <= n <= 100000)

然后是 n 个整数 ai。(|ai| <= 10000)

输出

针对每组案例,输出改变数字位置后可以得到的最大数组贡献值,然后换行。

样例输入

2
4
1 2 1 2
4
1 1 2 2

样例输出

8
8

HINT

注意:数组也可以不发生改变。

对于样例1:1 2 1 2

改变前数组的贡献值为 1 * 2 + 2 * 2 = 6

你可以把他改为 1 1 2 2 或者 2 2 1 1 得到更大的数组的贡献值 8。

来源
20-21(2)第0次线上赛