F. Mad MAD Sum II
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an integer array $$$a$$$ of length $$$n$$$, your task is to find the value of $$$\sum_{1 \le l \lt r \le n} \operatorname{MAD}([a_l,a_{l+1}, \ldots, a_r])$$$.

The $$$\operatorname{MAD}$$$ in an array is the largest value that appears at least twice in the array. If every value appears exactly once in the array, then its $$$\operatorname{MAD}$$$ value is $$$0$$$.

For example, $$$\operatorname{MAD}([1, 2, 2, 5, 5]) = 5$$$ and $$$\operatorname{MAD}([1, 2, 5]) = 0$$$.

Input

The first line of the input contains exactly one integer, $$$t$$$ $$$(1 \le t \le 3 \cdot 10^4)$$$, the number of testcases.

The first line of each testcase contains exactly one integer, $$$n$$$ $$$(2 \le n \le 2 \cdot 10^5)$$$, the length of the array.

The second line of each testcase contains exactly $$$n$$$ integers, $$$a_1, a_2, ..., a_n$$$ $$$(1 \le a_i \le 10^8)$$$.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$ over all testcases.

Output

For each test case, output an integer in a new line — $$$\sum_{1 \le l \lt r \le n} \operatorname{MAD}([a_l,a_{l+1}, \ldots, a_r])$$$.

Example
Input
3
2
1 2
4
4 2 2 4
8
5 2 1 2 1 5 2 1
Output
0
10
40
Note

In the first test case, $$$$$$\sum_{1 \le l \lt r \le n} \operatorname{MAD}([a_l,a_{l+1}, \ldots, a_r])=\operatorname{MAD}([a_1,a_2])=\operatorname{MAD}([1,2])=0. $$$$$$

In the second test case, the following table summarizes the $$$\operatorname{MAD}$$$ of each subarray. $$$$$$ \begin{array}{c|cccc} & 1 & 2 & 3 & 4 \\ \hline 1 & & 0 & 2 & 4 \\ 2 & & & 2 & 2 \\ 3 & & & & 0 \\ 4 & & & & \end{array} $$$$$$ The sum of all $$$\operatorname{MAD}$$$ values is $$$10$$$.