题目描述

两个版本之间的唯一区别是，在这个版本中，$n≤2\times 10^5$，并且所有测试用例的 $n$ 之和不超过 $2\times 10^5$。

接线端是一行 $n$ 个相等的线段，按顺序编号为 $1$ 到 $n$。在本例中，有两排接线端，一排在上，一排在下。

给你一个长度为 $n$ 的数组 $a$。对于所有 $i＝1,2,…,n$，应该有一条电线从顶部接线端的第 $i$ 段上的某一点到底部接线端的第 $a_i$ 段上的某个点（不能选择线段的端点）。例如，下图显示了 $n=7$ 和 $a=[4,1,4,6,7,7,5]$ 时的两种可能布线。

当两条电线可能会发生交叉。在上图中，交叉点用红色圆圈表示。（电线不弯曲）

在所有的布线方式中，最大交叉数是多少？

输入格式

第一行包含整数 $t(1≤t≤1000)$ 表示测试用例数。

每个测试用例的第一行包含一个整数 $n(1≤n≤2\times 10^5)$ 表示数组的长度。

每个测试用例的第二行包含 $n$ 整数 $a_1,a_2,…,a_n(1≤a_i≤n)$ 表示数组的元素。

所有测试用例的 $n$ 之和不超过 $2\times 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示可以达到的最大交叉数。

测试样例

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

6
1
0
3

样例说明

第一个测试用例展示在右侧图片中。

在第二个测试用例中，唯一可能的布线是两条线交叉，因此答案是 $1$。

在第三个测试用例中，唯一可能的布线只有一条线，因此答案为 $0$。