Count inversions

//Count inversions

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

class Sorting {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        for(int g = 0; g < t; g++) {
            String[] str = (br.readLine()).trim().split(" ");
            int arr[] = new int[str.length];

            for(int i = 0; i < str.length; i++) {
                arr[i] = Integer.parseInt(str[i]);
            }

            System.out.println(new Solution().inversionCount(arr));
            System.out.println("~");
        }
    }
}

class Solution {
    static int inversionCount(int arr[]) {
        return countInv(arr, 0, arr.length - 1);
    }
    
    static int countAndMerge(int[] arr, int l, int m, int r) {
        int n1 = m - l + 1, n2 = r - m;
        int[] left = new int[n1];
        int[] right = new int[n2];
        
        for(int i = 0; i < n1; i++) {
            left[i] = arr[i + l];
        }
        
        for(int j = 0; j < n2; j++) {
            right[j] = arr[m + 1 + j];
        }

        int res = 0;
        int i = 0, j = 0, k = l;
        
        while(i < n1 && j < n2) {
            if(left[i] <= right[j]) {
                arr[k++] = left[i++];
            }
            else {
                arr[k++] = right[j++];
                res += (n1 - i);
            }
        }

        while(i < n1) {
            arr[k++] = left[i++];
        }
        
        while(j < n2) {
            arr[k++] = right[j++];
        }

        return res;
    }

    static int countInv(int[] arr, int l, int r) {
        int res = 0;
        
        if(l < r) {
            int m = (r + l) / 2;
            res += countInv(arr, l, m);
            res += countInv(arr, m + 1, r);
            res += countAndMerge(arr, l, m, r);
        }
        
        return res;
    }
}