Description

给定一个长度为 $n$ 的排列 $A$。现使用如下伪代码对 $A$ 进行排序：

procedure QUICKSORT(A,lo,hi)
    if lo>=0 and hi>=0 and lo<hi then
    	p=PARTITION(A,lo,hi)
        QUICKSORT(A,lo,p)
        QUICKSORT(A,p+1,hi)
    end if
end procedure
procedure PARTITION(A,lo,hi)
    pivot=A[floor((hi+lo)/2)]
    i=lo-1
    j=hi+1
    while True do
        repeat
            i=i+1
        until A[i]>=pivot
        repeat
            j=j-1
        until A[j]<=pivot
        if i>=j then
            return j
        end if
        Swap A[i] with A[j]
    end while
end procedure

试计算：调用 QUICKSORT(A,1,n) 函数过程中，Swap 操作执行了多少次。

Input Format

第一行包含一个整数 $T$ $(1\leqslant T\leqslant 10^5)$，表示测试数据组数。

对于每组测试数据：

第一行包含一个正整数 $n$ $(1\leqslant n\leqslant 5\times 10^5)$。

第二行包含 $n$ 个整数 $a_1,\dots,a_n$ $(1\leqslant a_i\leqslant n)$，表示排列 $A$。保证 $a_1,\dots,a_n$ 构成一个排列，即：$\forall i\not= j,a_i\not=a_j$。

保证所有测试数据中 $n$ 的和不超过 $5\times 10^5$。

Output Format

对于每组测试数据，输出一行一个整数，表示调用 QUICKSORT(A,1,n) 函数过程中，Swap 操作执行的次数。

3
3
3 2 1
5
2 4 5 3 1
10
7 2 4 6 1 9 10 8 5 3

1
4
7