CF1676H2.Maximum Crossings (Hard Version)

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

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

You are given an array $a$ of length $n$. For all $i = 1, 2, \dots, n$, there should be a straight wire from some point on segment $i$ of the top terminal to some point on segment $a_i$ of the bottom terminal. You can't select the endpoints of a segment. For example, the following pictures show two possible wirings if $n=7$ and $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?

两个版本的唯一区别在于，本版本中 $n \leq 2 \cdot 10^5$，且所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

终端是一行 $n$ 个等长线段，按顺序编号为 $1$ 至 $n$。共有两个终端，一个位于另一个正上方。

给定一个长度为 $n$ 的数组 $a$。对每个 $i = 1, 2, \dots, n$，需从上侧终端的第 $i$ 段上的某一点（不能选端点）连一条直线导线，到下侧终端的第 $a_i$ 段上的某一点（同样不能选端点）。例如，下图展示了当 $n=7$ 且 $a=[4,1,4,6,7,7,5]$ 时两种可能的布线方式：

当两条导线存在公共交点时，即产生一次交叉。上图中所有交叉点均以红色圆圈标出。

若可自由选择各导线在对应线段上的连接位置（端点除外），则最多能产生多少次交叉？

The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

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

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq n$) — the elements of the array.

The sum of $n$ across all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \leq t \leq 1000$）—— 表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）—— 表示数组的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq n$）—— 表示数组的元素。

所有测试用例中 $n$ 的总和不超过 $2 \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.

对于每个测试用例，输出一个整数——即在最优布线方式下，导线交叉点的最大数量。

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 $1$.

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

第一个测试用例如题面中的第二张图片所示。

在第二个测试用例中，唯一可能的布线方式会导致两条导线相交，因此答案为 $1$。

在第三个测试用例中，唯一可能的布线方式仅包含一条导线，因此答案为 $0$。