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$$$:
1. Set $$$sum := sum + \sum_{i=1}^{n} a_i$$$;
2. 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.
Input Format:
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 Format:
For each test case, output the value of $$$sum$$$ in a new line.
Note:
In the first test case, $$$a=[1]$$$ initially.
In the first loop:
1. Set $$$sum := sum + a_1 = 0+1=1$$$;
2. 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$$$.