class Solution {
    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;

        // arr[0..n-1] = pairs (nums[i], i)
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i][0] = nums[i];
            arr[i][1] = i; // original index
        }

        // results[i] = count of smaller numbers a[j] after a[i] (j > i)
        List<Integer> results = new ArrayList<>();
        for (int i = 0; i < n; i++) results.add(0);

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

    public static void mergeSort(int[][] arr, int left, int right, List<Integer> results) {
        // If the subarray has only one element,
        // it doesn't have any inversions within it.
        if (left == right) return;

        int mid = (left + right) / 2;

        // Count all inversions such that the first element
        // is in the left half [left; mid] and the second is, too.
        mergeSort(arr, left, mid, results);

        // Count all inversions such that the first element
        // is in the right half [mid + 1; right] and the second is, too.
        mergeSort(arr, mid + 1, right, results);

        // Count all inversions such that the first element
        // is in the left half [left; mid] and the second
        // is in the right half [mid + 1; right].
        mergeSortedArrays(arr, left, right, results);
    }

    public static void mergeSortedArrays(int[][] arr, int left, int right, List<Integer> results) {
        int len = right - left + 1;

        int[][] tmp = new int[len][2];
        int[] updates = new int[len];

        int mid = (left + right) / 2;
        for (int k = 0, i = left, j = mid + 1; k < len; k++) {
            if (i > mid) tmp[k] = arr[j++];
            else if (j > right) tmp[k] = arr[i++];
            else if (arr[i][0] <= arr[j][0]) tmp[k] = arr[i++];
            else {
                tmp[k] = arr[j++];
                // Elements at indices [i; mid] from the left half
                // are forming inversions with the element at index j
                // in the right half, e.g. (arr[i][0], arr[j][0]) is an inversion,
                // (arr[i + 1][0], arr[j][0]) is an inversion, ...,
                // (arr[mid][0], arr[j][0]) is an inversion.
                // Hence, +1 needs to be added to results[arr[i][1]],
                // results[arr[i + 1][1]], ..., results[arr[mid][1]].
                // We put this +1 update for further computation into 'updates'.
                updates[i - left] += 1;
            }
        }

        int cumulative_updates = 0;
        for (int k = 0, i = left; i <= mid; k++, i++) { // iterate over the left half
            // compute cumulative update for each index arr[i][1]
            cumulative_updates += updates[k];

            // add the cumulative update to results[arr[i][1]]
            results.set(arr[i][1], results.get(arr[i][1]) + cumulative_updates);
        }

        for (int k = 0, i = left; k < len; k++, i++) {
            arr[i] = tmp[k];
        }
    }
}