28165번 - Cooperation Game 다국어

문제

Athletic contests in schools sometimes get too heated. To promote cooperation, the teachers have devised a game where cooperation leads to better scores.

This cooperation game starts with $N$ students standing in a line. To get a score, two students from the same class will get out of the line. If they were $i$-th and $j$-th students along the line, just before they went out, they add $|i - j|$ to the total score. The empty places of the two students that just came out will be compacted. The game stops when there are no more pairs of students from the same class.

For example, consider six students initially standing in a line:

$$ 1, 2, 3, 3, 2, 1 $$

The numbers are class numbers of the students. If the students come out from the line in the order of class number 1ドル,ドル then class number 2ドル,ドル then class number 3ドル,ドル the total score is 5ドル + 3 + 1 = 9$. However, in the same initial situation, if the students come out from the line in the order of 3ドル,ドル 2ドル,ドル 1ドル,ドル then the total score is 1ドル + 1 + 1 = 3$.

Given the class numbers in the initial line, write a program to calculate the maximum possible score.

입력

The first line contains an integer $T,ドル the number of test cases (1ドル \le T \le 48$). The test cases follow.

The first line of each test case contains a single integer $N,ドル the number of students (1ドル \le N \le 300,000円$).

In the next line, the sequence of class numbers are given. The class numbers are integers from 1ドル$ to $N$.

The sum of $N$ over all test cases does not exceed 7ドル,000円,000円$.

출력

For each test case, print a line with a single integer: the maximum possible score.

제한

힌트