← 返回题目列表

Codeforces · 1990/C

C. 疯狂疯狂总和

中文机器翻译题面 查看原题

我们将数组中的 $$$\operatorname{MAD}$$$ (Maximum Appearing Duplicate) 定义为在数组中至少出现两次的最大数字。具体来说,如果没有至少出现两次的数字,则 $$$\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$$$ 的值。

示例

输入 #1

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

输出 #1

1
13
9
40

注意

在第一个测试用例中,最初 $$$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$$$。