ArrayInversions.java

import java.util.Scanner;
import java.util.ArrayList;
public class Inversions {
    static long total = 0;
    
    public static int[] inversions(int a[],int s,int e)
    {
        if(a.length <= 1)
        return a;
        
        int n1 = (e-s+1)/2;
        int n2 = e-s+1-n1;
        int n = a.length;
        
        int[] a1 = new int[n1];
        int[] a2 = new int[n2];
        
        int i=0;
        for(;i<n1;i++)
        a1[i] = a[i];
        
        for(int j=0;j<n2 ; j++)
        a2[j] = a[j+i];
        
        inversions(a1,0,n1-1);
        inversions(a2,0,n2-1);
        
        int j=0,k=0;
        
        while(j<n1 && k < n2)
        {
            if(a1[j] <= a2[k])
            {
                a[j+k] = a1[j];
                j++;
            }
            else{
                a[j+k] = a2[k];
                k++;
                total = total + n1 - j;
            }
            
        }

            while(j<n1)
            {
                a[j+k] = a1[j];
                j++;
                ///total++;
            }

            while(k<n2)
            {
                a[k+j] = a2[k];
                k++;
            }

        return a;
    }
    
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> ar = new ArrayList<Integer>();
        while(sc.hasNextInt())
        {
            ar.add(sc.nextInt());
        }
        
        int a[] = new int[ar.size()];
        int n = ar.size();
        for(int i=0;i<n;i++)
        a[i] = ar.get(i);
        
        inversions(a,0,a.length-1);
        
        System.out.println(total);
    }
}