Insertion Sort Advanced Analysis

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 kkii is the number of elements over which the iithth element of the array has to shift, then the total number of shifts will be kk11 +k+k22 +...+k+...+kNN.

Input Format

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

Output Format

Output TT lines containing the required answer for each test case.

Constraints

1≤T≤151≤T≤15
1≤N≤1000001≤N≤100000
1≤a[i]≤10000000

Sample Input

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

Sample Output

0 
4  

Explanation
The first test case is already sorted, therefore there's no need to shift any element. In the second case, it will proceed in the following way.

Array: 2 1 3 1 2 -> 1 2 3 1 2 -> 1 1 2 3 2 -> 1 1 2 2 3
Moves:   -        1       -    2         -  1            = 4

solution: :

 #include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int read(int * p, int k) {
    int nrt=0;
    while(k>0) {
        nrt += p[k];
        k -= (k&(-k));
    }
    return nrt;
}

void update(int * p, int k) {
    while(k<=10000000) {
        p[k] ++;
        k += (k&(-k));
    }
}

int assign(int k, int * p, int existing) {
    int n = read(p, k); // sum of counts of number which is not bigger than k
    update(p, k);
    return existing-n;
}
int main() {
     int test=0;
    cin>>test;
    for(int i=0; i<test; i++) {
        int n=0;
        long sum=0l;
        cin>>n;
        int *p = new int[10000001]; // array is too big for stack
        for(int j=0; j<10000001; j++) {
            p[j]=0;
        }
      
        for(int j=0; j<n; j++) {
            int k=0;
            cin>>k;
            sum += assign(k, p, j);
        }
        cout<<sum<<endl;


delete[] p;
    }
    return 0;
}