K. Killed by Sorting
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

A suspicious streamer named TLE Creators proposed an algorithm to sort a permutation. Note that the code below uses one-indexed positions. 

Function CyclicSort(arr):
     pos = 1
     WHILE (arr is not sorted) DO
        index = find the index of the minimum element in arr[pos...n]
        shifts = index - pos
        FOR (i = 1...shifts) DO
            cyclically shift left arr[pos...n] by one position
        END
        pos = pos + 1
     END  
END

Let's consider an example by performing CyclicSort on the permutation $$$p = [2,4,1,3,5]$$$.

  • pos $$$=1$$$. The minimum element is at position $$$3$$$ ($$$p_3 = 1$$$), and the subarray $$$p_{1\cdots 5}$$$ is cyclically shifted to the left by one position twice, incurring $$$2$$$ operations. The resulting array is $$$p^{(1)} = [1,3,5,2,4]$$$.
  • pos $$$=2$$$. The minimum element is at position $$$4$$$ ($$$p^{(1)}_4 = 2$$$), and the subarray $$$p_{2\cdots 5}^{(1)}$$$ is cyclically shifted to the left by one position twice, incurring $$$2$$$ operations. The resulting array is $$$p^{(2)} = [1,2,4,3,5]$$$.
  • pos $$$=3$$$. The minimum element is at position $$$4$$$ ($$$p^{(2)}_4 = 3$$$), and the subarray $$$p_{3\cdots 5}^{(2)}$$$ is cyclically shifted to the left by one position once, incurring $$$1$$$ operation. The resulting array is $$$p^{(3)} = [1,2,3,5,4]$$$.
  • pos $$$=4$$$. The minimum element is at position $$$5$$$ ($$$p^{(3)}_5 = 4$$$), and the subarray $$$p_{4\cdots 5}^{(3)}$$$ is cyclically shifted to the left by one position once, incurring $$$1$$$ operation. The resulting array is $$$p^{(4)} = [1,2,3,4,5]$$$.
  • Since the array is sorted, the algorithm terminates.

TLE Creators proved that CyclicSort always sorts any permutation in ascending order, but they are having difficulty determining the number of cyclic left-shift operations that CyclicSort will perform. They are going live right after your contest, and desperately need your help!

Given a permutation $$$p$$$ of length $$$n$$$, please help TLE Creators determine the number of cyclic left-shift operations that CyclicSort will perform.

Input

The first line contains a single integer $$$t$$$ ($$$1\leq t \leq 10^3$$$), the number of test cases. For each test case,

  • The first line contains a single integer $$$n$$$ ($$$1\leq n \leq 2\times 10^5$$$), the length of the permutation $$$p$$$.
  • The second line contains $$$n$$$ integers $$$p_1$$$ $$$p_2$$$ $$$\cdots$$$ $$$p_n$$$ ($$$1\leq p_i \leq n$$$), where $$$p_i$$$ is the $$$i$$$-th value of the permutation $$$p$$$. It is guaranteed that $$$p$$$ is a permutation of $$$1,2,\cdots, n$$$.
The sum of $$$n$$$ over all test cases will not exceed $$$2\times 10^5$$$.
Output

$$$t$$$ lines. For each test case, output a single integer, the number of cyclic left-shift operations performed by CyclicSort.

Example
Input
4
5
2 4 1 3 5
6
2 3 1 4 5 6
6
6 5 4 3 2 1
7
1 2 3 4 5 6 7
Output
6
5
15
0
Note

There are $$$4$$$ test cases.

  • The first test case is illustrated in the statement. The total number of shift operations is $$$2 + 2 + 1 + 1 = 6$$$
  • In the second test case, the array transitions and cyclic left shift counts are as follows:
    • $$$p^{(1)} = [1,4,5,6,2,3]$$$, cyclic left shift count = 2
    • $$$p^{(2)} = [1,2,3,4,5,6]$$$, cyclic left shift count = 3
    Therefore the total number of shifts is $$$5$$$.