解题思路

先把题意重新整理一下。

对于一个子数组 $t$：

• 记某个数 $x$ 在 $t$ 中的出现次数为 $\operatorname{cnt}(x)$。
• 若一个数 $v$ 满足：对于任意 $v'$，都有 $\operatorname{cnt}(v)\ge \operatorname{cnt}(v')$，那么称 $v$ 支配这个子数组。
• 如果有多个数出现次数并列最多，则取数值最大的那个作为支配值。

题目内容

给定一个数组 $t$，定义任意数 $x$ 在 $t$ 中的出现次数为 $cnt(x)$。称 $t$ 被 $v$ 支配，当目仅当对任意 $v'$ 有 $cnt(v)≥cnt(v')$；若出现次数相同，则取数值最大的那个 $v$。定义数组 $t$ 的权值为 $v×|t|$(其中 $|t|$ 为 $t$ 的长度)

现在给定一个长度为 $n$ 的数组 $a_1,a_2,...,a_n$ 你需要将其划分为若干个非空续子数组，使得各子数组权值之和最小，输出该最小值。

【子数组】：子数组为原数组中任意一个连续且非空的元素区间。

输入描述

输入包含多组测试数据。

数据描述如下:

第一行包含整数 $T(1≤T≤10^3)$ 表示测试组数。每组第一行包含一个整数 $n(1≤n≤2×10^3)$

第二行包含 $n$ 个整数，表示数组 $a_1,a_2,....a_n(-10^9≤a_i≤10^9)$

保证所有测试中 $n$ 的总和不超过 $5×10^3$

输出描述

对于每组测试数据，输出一行一个整数，表示将数组划分为若干非空连续子数组后权值之和的最小值。

样例1

输入

3
5
1 1 2 2 3
3 
5 5 5
4
1 2 3 4

输出

8
15
10

说明

样例一：一种最优划分为 $[1,1,2],[2],[3]$，权值分别为 $1×3，2×1，3×1$，总和$3+2+3=8$

样例二：任意划分总和均为 $5×3=15$。

样例三：将其划分为单点 $[1],[2],[3],[4],$ 总和 $1+2+3+4=10$