HackerRank Insertion Sort Advanced Analysis problem solution

from array import array
from bisect import bisect_right

t = int(input())
for _ in range(t):
    n = int(input())
    arr = array('I', [int(i) for i in input().split()])
    sarr = array('I', [arr[0]])
    result = 0
    for i in range(1, n):
        e = arr[i]
        j = bisect_right(sarr, e)       
        sarr.insert(j, e)
        result += i - j
    print(result)            

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

public class Solution {
    private static final int MAXVAL = 10000000;
    private static int[] array = new int[MAXVAL+1];

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner sc = new Scanner(System.in);
        int testCaseCount = sc.nextInt();
        for (int i = 0; i < testCaseCount; i++) {
            int size = sc.nextInt();
            long sum = 0;
            Arrays.fill(array, 0);
            for (int j = 0; j < size; j++) {
                 sum += assign(sc.nextInt(), array, j);
            }
            System.out.println(sum);
        }
    }
    private static int assign(int x, int[] prefixSums, int current) {
        int n = read(prefixSums, x);
        update(prefixSums, x);
        return current-n;
    }

    private static int read(int[] prefixSums, int x) {
        int nrt=0;
        while(x>0) {
            nrt += prefixSums[x];
            x -= (x&(-x));
        }
        return nrt;
    }

    private static void update(int[] prefixSums, int x) {
        while(x <= MAXVAL) {
            prefixSums[x]++;
            x += (x&(-x));
        }
    }
}

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std ;
#define MAXN 100002
#define MAX 1000002
int n,a[MAXN],c[MAX] ;
int main()
{
 int runs ;
 scanf("%d",&runs) ;
 while(runs--)
 {
  scanf("%d",&n) ;
  for(int i = 0;i < n;i++) scanf("%d",&a[i]) ;
  long long ret = 1LL * n * (n - 1) / 2 ;
  memset(c,0,sizeof c) ;
  for(int i = 0;i < n;i++)
  {
   for(int j = a[i];j > 0;j -= j & -j) ret -= c[j] ;
   for(int j = a[i];j < MAX;j += j & -j) c[j]++ ;  
  }
  cout << ret << endl ;
 }
 return 0 ;
}

#include <stdio.h>
#include <string.h>
long long inv(int *A, int N)
{
	if(N <= 1) return 0;
	int m = N/2;
	long long ans = inv(A, m) + inv(A + m, N - m);
	static int tmp[100000];
	int left = 0, right = m, i;
	for(i = 0; i < N; i ++)
	{
		int min = 1000001;
		if(m - left > 0 && min > A[left])
			min = A[left++];
		if(N - right > 0 && min > A[right])
		{
			if(min != 1000001) left --;
			min = A[right++];
			ans += m - left;
		}
		tmp[i] = min;
	}
	memcpy(A, tmp, sizeof(int)*N);
	return ans;
}
void solve()
{
	int N;
	static int A[1000005];
	scanf("%d",&N);
	int i;
	for(i = 0; i < N; i ++) scanf("%d",A + i);
	printf("%lldn",inv(A,N));
}
int main()
{
	int K;
	scanf("%d",&K);
	while(K--) solve();
	
	return 0;
}