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 nondescending 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
the_ashutosh:
20190308 07:47:01
just count the inversions in the array.....using bit or segment tree 

karan_yadav:
20180717 07:28:17
This question screams merge sort tree, though you don't have to create the whole tree. Just sorting would do.


karthik1997:
20171227 16:47:21
BIT was much faster than mergesort trick , and be careful with \n at the end. it costed me many WA's :) 

ANKIT JAIN:
20170506 12:16:07
Solved using BIT :) 

vaibhavk31:
20170331 14:54:30
Test cases are weak


surayans tiwari(http://bit.ly/1EPzcpv):
20160914 14:38:09
policy based data structure! but the time limit needs to be improves even a brute force insertion sort passes! Last edit: 20160914 17:00:43 

ওয়াসী (Wasi):
20130525 13:45:52
I'm just a novice solver but through my perspective, Mitch is right.


Mitch Schwartz:
20130525 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:
20111023 12:50:05
Don't take the name of the problem too seriously :P 
Added by:  Varun Jalan 
Date:  20111015 
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 