CF1990C.Mad MAD Sum

我们定义数组中的 $ \operatorname{MAD} $（最大重复出现数）为数组中出现至少两次的最大数字。具体来说，如果没有任何数字出现至少两次，则 $ \operatorname{MAD} $ 的值为 $ 0 $。

例如，$ \operatorname{MAD}([1, 2, 1]) = 1 $，$ \operatorname{MAD}([2, 2, 3, 3]) = 3 $，$ \operatorname{MAD}([1, 2, 3, 4]) = 0 $。

给定一个长度为 $ n $ 的数组 $ a $。初始时，有一个变量 $ sum $，其值为 $ 0 $。

执行如下过程，直到 $ a $ 中所有数字都变为 $ 0 $ 为止，循环进行：

1. 令 $ sum := sum + \sum_{i=1}^{n} a_i $；
2. 令 $ b $ 为长度为 $ n $ 的数组。对于所有 $ 1 \le i \le n $，令 $ b_i :=\ \operatorname{MAD}([a_1, a_2, \ldots, a_i]) $，然后对于所有 $ 1 \le i \le n $，令 $ a_i := b_i $。

请你求出该过程结束后 $ sum $ 的值。

第一行包含一个整数 $ t $（$ 1 \leq t \leq 2 \cdot 10^4 $），表示测试用例的数量。

对于每个测试用例：

• 第一行包含一个整数 $ n $（$ 1 \leq n \leq 2 \cdot 10^5 $），表示数组 $ a $ 的长度；
• 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 1 \leq a_i \leq n $），表示数组的元素。

保证所有测试用例中 $ n $ 的总和不超过 $ 2 \cdot 10^5 $。

对于每个测试用例，输出一个整数，表示该过程结束后 $ sum $ 的值，每个测试用例输出一行。

在第一个测试用例中，初始时 $ a=[1]$。

第一次循环：

1. 令 $ sum := sum + a_1 = 0+1=1 $；
2. 令 $ b_1 :=\ \operatorname{MAD}([a_1])=\ \operatorname{MAD}([1])=0 $，然后令 $ a_1 := b_1 $。

第一次循环后，$ a=[0] $，过程结束。最终 $ sum=1 $。

在第二个测试用例中，初始时 $ a=[2,2,3]$。

第一次循环后，$ a=[0,2,2] $，$ sum=7 $。

第二次循环后，$ a=[0,0,2] $，$ sum=11 $。

第三次循环后，$ a=[0,0,0] $，$ sum=13 $，过程结束。

最终 $ sum=13 $。

由 ChatGPT 4.1 翻译