CODESPTB - Insertion Sort


Insertion Sort is a classical sorting technique. One variant of insertion sort works as follows when sorting an array a[1..N] in non-descending order:

for i <- 2 to N
    j <- i
    while j > 1 and a[j] < a[j - 1]
        swap a[j] and a[j - 1]
        j <- j - 1

The pseudocode is simple to follow. In the ith step, element a[i] is inserted in the sorted sequence a[1..i - 1]. This is done by moving a[i] backward by swapping it with the previous element until it ends up in it's right position.

As you probably already know, the algorithm can be really slow. To study this more, you want to find out the number of times the swap operation is performed when sorting an array.

Input

The first line contains the number of test cases T. T test cases follow. The first line for each case contains N, the number of elements to be sorted. The next line contains N integers a[1],a[2]...,a[N].

Output

Output T lines, containing the required answer for each test case.

Constraints

1 <= T <= 5
1 <= N <= 100000
1 <= a[i] <= 1000000

Example

Sample Input:
2
5
1 1 1 2 2
5
2 1 3 1 2

Sample Output:
0
4

hide comments
ANKIT JAIN: 2017-05-06 12:16:07

Solved using BIT :)

vaibhavk31: 2017-03-31 14:54:30

Test cases are weak
even naive one gets passed !! :)

surayans tiwari(http://bit.ly/1EPzcpv): 2016-09-14 14:38:09

policy based data structure! but the time limit needs to be improves even a brute force insertion sort passes!

Last edit: 2016-09-14 17:00:43
ওয়াসী (Wasi): 2013-05-25 13:45:52

I'm just a novice solver but through my perspective, Mitch is right.
I don't know about others but I thought this problem is different than the [...] at my first look.

Last edit: 2014-10-30 22:40:09
Mitch Schwartz: 2013-05-25 13:27:24

The other problem that everyone refers to has a somewhat different problem statement, and I think it would not be obvious to many that they are equivalent if not for the comments. So a case can be made that they are spoilers and should be censored. Opinions?

Aradhya Tulsyan: 2011-10-23 12:50:05

Don't take the name of the problem too seriously :P


Added by:Varun Jalan
Date:2011-10-15
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem used for CodeSprint - InterviewStreet Contest