B. 23 Kingdom

The distance of a value in an array , denoted as , is defined as the largest gap between any two occurrences of in .

Formally, over all pairs where . If appears only once or not at all in , then .

The beauty of an array is the sum of the distances of each distinct value in the array. Formally, the beauty of an array is equal to .

Given an array of length , an array is nice if it also has length and its elements satisfy for all . Your task is to find the maximum possible beauty of any nice array.

Each test contains multiple test cases. The first line contains the number of test cases ( ). The description of the test cases follows.

The first line of each test case contains a single integer ( ) — the length of array .

The second line of each test case contains integers ( ) — the elements of array .

It is guaranteed that the sum of over all test cases does not exceed .

For each test case, output a single integer representing the maximum possible beauty among all nice arrays.

输入 #1

4
4
1 2 1 2
2
2 2
10
1 2 1 5 1 2 2 1 1 2
8
1 5 2 8 4 1 4 2

输出 #1

4
1
16
16

In the first test case, if , then and , resulting in a beauty of . It can be proven that there are no nice arrays with a beauty greater than .

In the second test case, both and are valid solutions with a beauty of .

In the third test case, if with , , and , resulting in a beauty of .