CF1990C Mad MAD Sum

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.

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.

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 $ .