#P1676H2. Maximum Crossings (Hard Version)

    ID: 7703 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>data structuresdivide and conquersortings*1500

Maximum Crossings (Hard Version)

Description

The only difference between the two versions is that in this version n2105n \leq 2 \cdot 10^5 and the sum of nn over all test cases does not exceed 21052 \cdot 10^5.

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

You are given an array aa of length nn. For all i=1,2,,ni = 1, 2, \dots, n, there should be a straight wire from some point on segment ii of the top terminal to some point on segment aia_i of the bottom terminal. For example, the following pictures show two possible wirings if n=7n=7 and a=[4,1,4,6,7,7,5]a=[4,1,4,6,7,7,5].

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 tt (1t10001 \leq t \leq 1000) — the number of test cases.

The first line of each test case contains an integer nn (1n21051 \leq n \leq 2 \cdot 10^5) — the length of the array.

The second line of each test case contains nn integers a1,a2,,ana_1, a_2, \dots, a_n (1ain1 \leq a_i \leq n) — the elements of the array.

The sum of nn across all test cases does not exceed 21052 \cdot 10^5.

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 tt (1t10001 \leq t \leq 1000) — the number of test cases.

The first line of each test case contains an integer nn (1n21051 \leq n \leq 2 \cdot 10^5) — the length of the array.

The second line of each test case contains nn integers a1,a2,,ana_1, a_2, \dots, a_n (1ain1 \leq a_i \leq n) — the elements of the array.

The sum of nn across all test cases does not exceed 21052 \cdot 10^5.

Output

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

Samples

样例输入 1

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

样例输出 1

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.