Part 7 of 15 in Sorting  

How many shifts in insertion sort? by animeshn

Problem statement

Given a list of integers, find out how many shifts it will take to sort the list using insertion sort algorithm.

Input

First line of input will contain a positive integer T = number of test cases. Each test case will contain 2 lines. First line will contain a positive integer N = number of elements in a list. Next line will contain N space separated integers. There will be no duplicate in a list.

Output

For each test case, print on a single line the total number of shifts performed while sorting the list using insertion sort algorithm. A shift is any change in position of an element in the list while performing insertion sort.

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

Sample Output
5
54
0

Explanation

2,4,1,3,5 => 2,4,1,3,5 (0 shifts) => 1,2,4,3,5 (3 shifts - any change in position is shift) => 1,2,3,4,5 (2 shifts) - total 5 shifts



To try out your code



Sign in

Sign up