## 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```

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````import java.io.*;
import java.util.*;

class A{
public static void main(String[] args) {
final OutputWriter out = new OutputWriter(System.out);
SolveA sol = new SolveA();
while(t-- > 0){
sol.solve(in, out);
}
out.flush();
out.close();
}
}
class SolveA{
long merge(int[] arr1, int[] arr2, int[] arr3){
int i = 0;
int j = 0;
int k = 0;
long countInv = 0;
while(i < arr1.length && j < arr2.length){
if(arr1[i] <= arr2[j]){
arr3[k] = arr1[i];
i++;
}else{
arr3[k] = arr2[j];
countInv+=(long)arr1.length-i;
j++;
}
k++;
}
while(i < arr1.length){
arr3[k] = arr1[i];
i++;
k++;
}
while(j < arr2.length){
arr3[k] = arr2[j];
j++;
k++;
}
return countInv;
}
long mergeAndCountInv(int[] arr){
if(arr.length<=1)
return (long)0;
int[] left = new int[arr.length/2];
int[] right = new int[arr.length-left.length];
for(int i = 0;i < left.length; i++){
left[i] = arr[i];
}
for(int k = 0;k < right.length; k++){
right[k] = arr[left.length+k];
}
long leftInv = mergeAndCountInv(left);
long rightInv = mergeAndCountInv(right);
long mergeInv = merge(left, right, arr);
return leftInv+rightInv+mergeInv;
}
final int[] arr = new int[n];
for(int i = 0;i < n; i++){
}
long count = mergeAndCountInv(arr);
out.printLine(count);
}

}
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;

{
this.stream = stream;
}

{
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars)
{
curChar = 0;
try
{
} catch (IOException e)
{
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}

{
while (isSpaceChar(c))
int sgn = 1;
if (c == '-')
{
sgn = -1;
}
int res = 0;
do
{
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
} while (!isSpaceChar(c));
return res * sgn;
}

{
while (isSpaceChar(c))
StringBuilder res = new StringBuilder();
do
{
res.appendCodePoint(c);
} while (!isSpaceChar(c));
return res.toString();
}
while (isSpaceChar(c))
int sgn = 1;
if (c == '-') {
sgn = -1;
}
double res = 0;
while (!isSpaceChar(c) && c != '.') {
if (c == 'e' || c == 'E')
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
}
if (c == '.') {
double m = 1;
while (!isSpaceChar(c)) {
if (c == 'e' || c == 'E')
if (c < '0' || c > '9')
throw new InputMismatchException();
m /= 10;
res += (c - '0') * m;
}
}
return res * sgn;
}
while (isSpaceChar(c))
int sgn = 1;
if (c == '-') {
sgn = -1;
}
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
} while (!isSpaceChar(c));
return res * sgn;
}
public boolean isSpaceChar(int c)
{
if (filter != null)
return filter.isSpaceChar(c);
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}

public String next()
{
}

public interface SpaceCharFilter
{
public boolean isSpaceChar(int ch);
}
}
class OutputWriter {
private  PrintWriter writer;
public OutputWriter(OutputStream outputStream)
{
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer)
{
this.writer = new PrintWriter(writer);
}
public void print(Object... objects)
{
for (int i = 0; i < objects.length; i++)
{
if (i != 0)
writer.print(' ');
writer.print(objects[i]);
}
}
public void printLine(Object... objects)
{
print(objects);
writer.println();
}
public void close()
{
writer.close();
}

public void flush()
{
writer.flush();
}
} ``````
Copy The Code &

Input

cmd
2
5
1 1 1 2 2
5
2 1 3 1 2

Output

cmd
0
4

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````#include<bits/stdc++.h>
using namespace std;
#define mx 1000005
int tree[mx*4];
void update(int pos, int b, int e, int i, int j)
{
if(b>e || b>j || e<i) return;
if(b>=i && e<=j){
tree[pos] = tree[pos]+1;
return;
}
int m = (b+e)/2;
int l = pos*2;
int r = l+1;
update(l,b,m,i,j);
update(r,m+1,e,i,j);
tree[pos] = tree[l] + tree[r];
}
int query(int pos, int b, int e, int i, int j)
{
if(b>e || b>j || e<i) return 0;
if(b>=i && e<=j) return tree[pos];
int m = (b+e)/2;
int l = pos*2;
int r = l+1;
int r1 = query(l,b,m,i,j);
int r2 = query(r,m+1,e,i,j);
return (r1+r2);
}
int main()
{
scanf("%d",&tc);
while(tc--){
long long ans = 0;
memset(tree, 0, sizeof tree);
scanf("%d",&n);
while(n--){
scanf("%d",&a);
update(1,1,mx-2,a,a);
}
printf("%lld\n",ans);
}
return 0;
}``````
Copy The Code &

Input

cmd
2
5
1 1 1 2 2
5
2 1 3 1 2

Output

cmd
0
4