[Solution] Maximum Crossings (Hard Version) solution codeforces – What is the maximum number of crossings there can be if you place the wires optimally?

Maximum Crossings (Hard Version) solution codeforces – The only difference between the two versions is that in this version 𝑛2105n≤2⋅105 and the sum of 𝑛n over all test cases does not exceed 21052⋅105.

[Solution] Maximum Crossings (Hard Version) solution codeforces

terminal is a row of 𝑛n equal segments numbered 11 to 𝑛n in order. There are two terminals, one above the other.

You are given an array 𝑎a of length 𝑛n. For all 𝑖=1,2,,𝑛i=1,2,…,n, there should be a straight wire from some point on segment 𝑖i of the top terminal to some point on segment 𝑎𝑖ai of the bottom terminal. For example, the following pictures show two possible wirings if 𝑛=7n=7 and 𝑎=[4,1,4,6,7,7,5]a=[4,1,4,6,7,7,5].

Maximum Crossings (Hard Version) solution codeforces
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?

[Solution] Maximum Crossings (Hard Version) solution codeforces

The first line contains an integer 𝑡t (1𝑡10001≤t≤1000) — the number of test cases.

The first line of each test case contains an integer 𝑛n (1𝑛21051≤n≤2⋅105) — the length of the array.

The second line of each test case contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖𝑛1≤ai≤n) — the elements of the array.

The sum of 𝑛n across all test cases does not exceed 21052⋅105.

Output

For each test case, output a single integer — the maximum number of crossings there can be if you place the wires optimally.

Example
input

Copy
4
7
4 1 4 6 7 7 5
2
2 1
1
1
3
2 2 2

[Solution] Maximum Crossings (Hard Version) solution codeforces

output

Copy
6
1
0
3
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 11.

In the third test case, the only wiring possible has one wire, so the answer is 00.

For Solution

Click here

Leave a Comment