题目内容

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$。你需要将它划分成若干个连续非空子段。对于每一个子段，定义其 主值 为在该子段中出现次数最多的整数；如果有多个整数并列出现次数最多，则取数值最大的那个。该子段的代价定义为主值乘以子段的长度。

请计算所有子段代价之和的最小可能值。

数据范围：测试数据组数不超过 1000。对于每组数据，数组长度 $n$ 不超过 2000，元素绝对值不超过 10^9。保证所有测试数据中 $n$ 的总和不超过 5000。

输入描述

第一行包含一个整数 $T$，表示测试数据组数。 接下来依次描述每组数据： 每组数据的第一行包含一个整数 $n$。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，相邻整数之间用一个空格分隔。 所有测试数据中 $n$ 的总和不超过 5000。

输出描述

对于每组测试数据，输出一行一个整数，表示最小总代价。

样例1

输入

1
1
-100

输出

-100

说明

只有一个元素 -100，只能划分为一段。该段中 -100 出现 1 次，主值为 -100，长度为 1，代价为 $(-100) \times 1 = -100$。因此最小总代价为 -100。

样例2

输入

1
3
-2 -2 3

输出

-6

说明

数组为 [-2, -2, 3]。考虑所有划分方案：

• 不划分，整个数组作为一段：-2 出现 2 次，3 出现 1 次，主值为 -2（出现次数最多）。代价为 $(-2) \times 3 = -6$。
• 划分为 [-2] 和 [-2, 3]：第一段代价 $(-2) \times 1 = -2$；第二段中 -2 和 3 各出现 1 次，主值取数值较大的 3，代价 $3 \times 2 = 6$，总代价 4。
• 划分为 [-2, -2] 和 [3]：第一段主值 -2，代价 $(-2) \times 2 = -4$；第二段代价 $3 \times 1 = 3$，总代价 -1。 比较得最小总代价为 -6。

样例3

输入

1
4
-5 2 -5 2

输出

-13

说明

数组 [-5, 2, -5, 2]。最优划分方案为 [-5, 2, -5] 和 [2]。

• 第一段 [-5, 2, -5]：-5 出现 2 次，2 出现 1 次，主值为 -5，代价 $(-5) \times 3 = -15$。
• 第二段 [2]：2 出现 1 次，代价 $2 \times 1 = 2$。 总代价 $-15 + 2 = -13$。若不划分，整个数组的主值为 2（-5 与 2 均出现 2 次，取数值大的 2），代价 $2 \times 4 = 8$，大于 -13。