package bonus;

import java.util.Arrays;

public class Main {
	private static int interclasare(int[] arr, int[] tempArr, int l, int m, int r) {
		int i = l, j = m, k = l, n = 0;

		while (i < m && j <= r) {
			if (arr[i] <= arr[j]) {
				tempArr[k++] = arr[i++];
			} else {
				tempArr[k++] = arr[j++];
				n += (m - i);
			}
		}

		while (i < m) {
			tempArr[k++] = arr[i++];
		}

		while (j <= r) {
			tempArr[k++] = arr[j++];
		}

		for (i = l; i <= r; i++) {
			arr[i] = tempArr[i];
		}

		return n;
	}

	private static int mergeSort(int[] arr, int[] tempArr, int l, int r) {
		int n = 0;

		if (l < r) {
			int m = (l + r) / 2;

			n = n + mergeSort(arr, tempArr, l, m) + mergeSort(arr, tempArr, m + 1, r) + interclasare(arr, tempArr, l, m + 1, r);
		}

		return n;
	}

	public static void main(String[] args) {
		int[] arr = {0, 1, 9, 4, 5, 7, 6, 8, 2};
		System.out.println(mergeSort(arr, new int[arr.length], 0, arr.length - 1));
	}

}