public class Solution {

public long countInversions(int[] arr) {

return mergeSort(arr, 0, arr.length - 1);

}



private long mergeSort(int[] arr, int start, int end) {

if (start >= end) {

return 0;

}

int mid = start + (end - start) / 2;

int count = 0;

count += mergeSort(arr, start, mid);

count += mergeSort(arr, mid + 1, end);

count += merge(arr, start, mid, end);

return count;

}



private long merge(int[] arr, int start, int mid, int end) {

int left = start;

int right = mid + 1;

int[] tmp = new int[end - start + 1];

int k = 0;

int count = 0;

while (left<= mid && right<= end) {

if (arr[left] > arr[right]) {

// count inversions between left & right array

count += end - right + 1;

tmp[k++] = arr[left++];

} else {

tmp[k++] = arr[right++];

}

}



while (left<= mid) {

tmp[k++] = arr[left++];

}



while (right<= end) {

tmp[k++] = arr[right++];

}

// copy tmp to array, can replace

// by System.arraycopy method

for (int i = 0; i<tmp.length; i++) {

arr[i + start] = tmp[i];

}

return count;

}

}