CF1676H2 Maximum Crossings (Hard Version)

本版本与另一个版本的唯一区别在于，本题中 $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]$ 时的两种可能的连线方式。  当两根线有公共点时，称为一次“交叉”。在上图中，交叉点用红圈标出。 如果你可以最优地放置这些线，最多能有多少次交叉？

第一行包含一个整数 $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$。

对于每个测试用例，输出一个整数，表示在最优放置线的情况下，最多能有多少次交叉。

第一个测试用例如题面第二张图所示。 第二个测试用例中，唯一的连线方式会有两根线交叉，因此答案为 $1$。 第三个测试用例中，只有一根线，因此答案为 $0$。 由 ChatGPT 4.1 翻译