Maximum Crossings (Hard Version)最大交叉次数（困难版本）

time limit per test

1 second

memory limit per test

256 megabytes

The only difference between the two versions is that in this version n≤2⋅105n≤2⋅105 and the sum of nn over all test cases does not exceed 2⋅1052⋅105.

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,…,n, there should be a straight wire from some point on segment ii of the top terminal to some point on segment aiai of the bottom terminal. You can't select the endpoints of a segment. 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?

Input

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

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

The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤n1≤ai≤n) — the elements of the array.

The sum of nn across all test cases does not exceed 2⋅1052⋅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

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.

每个测试的时间限制 1 秒
每个测试的内存限制 256 兆字节
两个版本之间的唯一区别是，在这个版本中 n≤2⋅105
并且所有测试用例的 n
之和不超过 2⋅105
。

终端是一行 n
个相等的线段，按顺序编号为 1
到 n
。有两个终端，一个在另一个之上。

给定一个长度为 n
的数组 a
。对于所有 i=1,2,…,n
，应该有一条直线从顶部终端的线段 i
上的某个点到底部终端的线段 ai
上的某个点。您无法选择线段的端点。例如，如果 n=7
和 a=[4,1,4,6,7,7,5]
，以下图片显示了两种可能的布线。

当两根线共享一个共同点时，就会发生交叉。在上图中，交叉点用红色圆圈圈出。

如果以最佳方式放置电线，则最多可以有多少个交叉点？

输入
第一行包含一个整数 t
(1≤t≤1000
) — 测试用例的数量。

每个测试用例的第一行包含一个整数 n
(1≤n≤2⋅105
) — 数组的长度。

每个测试用例的第二行包含 n
个整数 a1,a2,…,an
(1≤ai≤n
) — 数组的元素。

所有测试用例的 n
之和不超过 2⋅105
。

输出
对于每个测试用例，输出一个整数 — 如果以最佳方式放置电线，则最多可以有多少个交叉点。

示例
InputCopy
4
7
4 1 4 6 7 7 5
2
2 1
1
1
3
2 2 2
OutputCopy
6
1
0
3
注意
第一个测试用例显示在语句中的第二张图片中。

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

在第三个测试用例中，唯一可能的接线是一根电线，因此答案是 0
。

 代码：
 

#include <iostream>
#include <vector>
using namespace std;

class FenwickTree {
public:
    FenwickTree(int n) : tree(n + 1, 0) {}

    void update(int idx, int delta) {
        while (idx < tree.size()) {
            tree[idx] += delta;
            idx += idx & (-idx);
        }
    }

    int query(int idx) {
        int sum = 0;
        while (idx > 0) {
            sum += tree[idx];
            idx -= idx & (-idx);
        }
        return sum;
    }

private:
    vector<int> tree;
};

int main() {
    int t;
    cin >> t;
    vector<long long> results(t);

    for (int test_case = 0; test_case < t; test_case++) {
        int n;
        cin >> n;
        vector<int> a(n);

        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        FenwickTree fenwick(n);
        long long result = 0;

        for (int i = n - 1; i >= 0; i--) {
            result += fenwick.query(a[i]);
            fenwick.update(a[i], 1);
        }

        results[test_case] = result;
    }

    for (long long result : results) {
        cout << result << endl;
    }

    return 0;
}