Mad MAD Sum
Description
We define the $\operatorname{MAD}$ (Maximum Appearing Duplicate) in an array as the largest number that appears at least twice in the array. Specifically, if there is no number that appears at least twice, the $\operatorname{MAD}$ value is $0$.
For example, $\operatorname{MAD}([1, 2, 1]) = 1$, $\operatorname{MAD}([2, 2, 3, 3]) = 3$, $\operatorname{MAD}([1, 2, 3, 4]) = 0$.
You are given an array $a$ of size $n$. Initially, a variable $sum$ is set to $0$.
The following process will be executed in a sequential loop until all numbers in $a$ become $0$:
- Set $sum := sum + \sum_{i=1}^{n} a_i$;
- Let $b$ be an array of size $n$. Set $b_i :=\ \operatorname{MAD}([a_1, a_2, \ldots, a_i])$ for all $1 \le i \le n$, and then set $a_i := b_i$ for all $1 \le i \le n$.
Find the value of $sum$ after the process.
The first line contains an integer $t$ ($1 \leq t \leq 2 \cdot 10^4$) — the number of test cases.
For each test case:
- The first line contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the size of the array $a$;
- The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$) — the elements of the array.
It is guaranteed that the sum of $n$ over all test cases will not exceed $2 \cdot 10^5$.
For each test case, output the value of $sum$ in a new line.
Input
The first line contains an integer $t$ ($1 \leq t \leq 2 \cdot 10^4$) — the number of test cases.
For each test case:
- The first line contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the size of the array $a$;
- The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$) — the elements of the array.
It is guaranteed that the sum of $n$ over all test cases will not exceed $2 \cdot 10^5$.
Output
For each test case, output the value of $sum$ in a new line.
4
1
1
3
2 2 3
4
2 1 1 2
4
4 4 4 4
1
13
9
40
Note
In the first test case, $a=[1]$ initially.
In the first loop:
- Set $sum := sum + a_1 = 0+1=1$;
- Set $b_1 :=\ \operatorname{MAD}([a_1])=\ \operatorname{MAD}([1])=0$, and then set $a_1 := b_1$.
After the first loop, $a=[0]$ and the process ends. The value of $sum$ after the process is $1$.
In the second test case, $a=[2,2,3]$ initially.
After the first loop, $a=[0,2,2]$ and $sum=7$.
After the second loop, $a=[0,0,2]$ and $sum=11$.
After the third loop, $a=[0,0,0]$ and $sum=13$. Then the process ends.
The value of $sum$ after the process is $13$.