Insertion Sort is a simple sorting technique which was covered in previous challenges. Sometimes, arrays may be too large for us to wait around for insertion sort to finish. Is there some other way we can calculate the number of times Insertion Sort shifts each elements when sorting an array?
If is the number of elements over which the element of the array has to shift, then the total number of shifts will be .
The first line contains a single integer, , denoting the number of queries to perform. The subsequent lines describe each query over two lines:
The first line contains an integer, , denoting the number of elements to be sorted.
The second line contains space-separated integers describing the respective values of .
Print lines containing the required answer for each query.
1 1 1 2 2
2 1 3 1 2
The first query is already sorted, therefore there's no need to shift any element. In the second case, it will proceed in the following way.