{"raw_statement":[{"iden":"statement","content":"When Prof. Pang was young, he wrote the following code for quick sort. Please calculate how many swaps are performed when calling $\\text{quicksort}(A, 1, n)$. $A$ is a given permutation with length $n$.\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/8ig9i3bq.png)"},{"iden":"input","content":"The first line contains one integer $T~(1\\le T \\le 10^5)$, the number of test cases.\n\nFor each test case, the first line contains one positive integer $n~(1\\le n \\le 5\\times 10^5)$. The next line contains $n$ integers $a_1,\\ldots, a_n~(1 \\le a_i\\le n)$ denoting the permutation $A$. It is guaranteed that $a_1,\\ldots, a_n$ form a permutation, i.e.~$a_i\\neq a_j$ for $i \\neq j$. \n\nIt is guaranteed that the sum of $n$ over all test cases is no more than $5\\times 10^5$."},{"iden":"output","content":"For each test case, output one line containing the number of swaps performed when calling $\\text{quicksort}(A, 1, n)$."}],"translated_statement":null,"sample_group":[["3\n3\n3 2 1\n5\n2 4 5 3 1\n10\n7 2 4 6 1 9 10 8 5 3","1\n4\n7"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}