#P1676H2. Maximum Crossings (Hard Version)
Maximum Crossings (Hard Version)
Description
The only difference between the two versions is that in this version and the sum of over all test cases does not exceed .
A terminal is a row of equal segments numbered to in order. There are two terminals, one above the other.
You are given an array of length . For all , there should be a straight wire from some point on segment of the top terminal to some point on segment of the bottom terminal. For example, the following pictures show two possible wirings if and .
A crossing occurs when two wires share a point in common. In the picture above, crossings are circled in red.
What is the maximum number of crossings there can be if you place the wires optimally?
The first line contains an integer () — the number of test cases.
The first line of each test case contains an integer () — the length of the array.
The second line of each test case contains integers () — the elements of the array.
The sum of across all test cases does not exceed .
For each test case, output a single integer — the maximum number of crossings there can be if you place the wires optimally.
Input
The first line contains an integer () — the number of test cases.
The first line of each test case contains an integer () — the length of the array.
The second line of each test case contains integers () — the elements of the array.
The sum of across all test cases does not exceed .
Output
For each test case, output a single integer — the maximum number of crossings there can be if you place the wires optimally.
Samples
Note
The first test case is shown in the second picture in the statement.
In the second test case, the only wiring possible has the two wires cross, so the answer is .
In the third test case, the only wiring possible has one wire, so the answer is .