Example 1:
Input:
arr = [8, 4, 2, 1]
Output: 6
Explanation: There are 6 inversions in the array: (8, 4), (8, 2), (8, 1), (4, 2), (4, 1), and (2, 1).

Example 2:
Input:
arr = [3, 1, 2]
Output: 2
Explanation: There are 2 inversions in the array: (3, 1) and (3, 2).

Example 3:
Input:
arr = [1, 2, 3, 4]
Output: 0
Explanation: The array is already sorted, so there are no inversions.

#include <iostream>
#include <vector>
using namespace std;

// Function to merge two halves and count inversions
int mergeAndCount(vector<int>& arr, vector<int>& temp, int left, int mid, int right) {
    int i = left;    // Starting index for left subarray
    int j = mid + 1; // Starting index for right subarray
    int k = left;    // Starting index to be sorted
    int inversions = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
            inversions += (mid - i + 1);
        }
    }

    while (i <= mid)
        temp[k++] = arr[i++];

    while (j <= right)
        temp[k++] = arr[j++];

    for (i = left; i <= right; i++)
        arr[i] = temp[i];

    return inversions;
}

// Function to recursively sort and count inversions
int mergeSortAndCount(vector<int>& arr, vector<int>& temp, int left, int right) {
    int inversions = 0;
    if (left < right) {
        int mid = (left + right) / 2;

        inversions += mergeSortAndCount(arr, temp, left, mid);
        inversions += mergeSortAndCount(arr, temp, mid + 1, right);
        inversions += mergeAndCount(arr, temp, left, mid, right);
    }
    return inversions;
}

// Function to count inversions in the array
int countInversions(vector<int>& arr) {
    vector<int> temp(arr.size());
    return mergeSortAndCount(arr, temp, 0, arr.size() - 1);
}

int main() {
    vector<int> arr = {8, 4, 2, 1};
    cout << "Number of inversions: " << countInversions(arr) << endl;
    return 0;
}

public class InversionCount {

    // Function to merge two halves and count inversions
    private static int mergeAndCount(int[] arr, int[] temp, int left, int mid, int right) {
        int i = left;    // Starting index for left subarray
        int j = mid + 1; // Starting index for right subarray
        int k = left;    // Starting index to be sorted
        int inversions = 0;

        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
                inversions += (mid - i + 1);
            }
        }

        while (i <= mid)
            temp[k++] = arr[i++];

        while (j <= right)
            temp[k++] = arr[j++];

        for (i = left; i <= right; i++)
            arr[i] = temp[i];

        return inversions;
    }

    // Function to recursively sort and count inversions
    private static int mergeSortAndCount(int[] arr, int[] temp, int left, int right) {
        int inversions = 0;
        if (left < right) {
            int mid = (left + right) / 2;

            inversions += mergeSortAndCount(arr, temp, left, mid);
            inversions += mergeSortAndCount(arr, temp, mid + 1, right);
            inversions += mergeAndCount(arr, temp, left, mid, right);
        }
        return inversions;
    }

    // Function to count inversions in the array
    public static int countInversions(int[] arr) {
        int[] temp = new int[arr.length];
        return mergeSortAndCount(arr, temp, 0, arr.length - 1);
    }

    public static void main(String[] args) {
        int[] arr = {8, 4, 2, 1};
        System.out.println("Number of inversions: " + countInversions(arr));
    }
}

# Function to merge two halves and count inversions
def merge_and_count(arr, temp, left, mid, right):
    i = left    # Starting index for left subarray
    j = mid + 1 # Starting index for right subarray
    k = left    # Starting index to be sorted
    inversions = 0

    while i <= mid and j <= right:
        if arr[i] <= arr[j]:
            temp[k] = arr[i]
            i += 1
        else:
            temp[k] = arr[j]
            inversions += (mid - i + 1)
            j += 1
        k += 1

    while i <= mid:
        temp[k] = arr[i]
        i += 1
        k += 1

    while j <= right:
        temp[k] = arr[j]
        j += 1
        k += 1

    for i in range(left, right + 1):
        arr[i] = temp[i]

    return inversions

# Function to recursively sort and count inversions
def merge_sort_and_count(arr, temp, left, right):
    inversions = 0
    if left < right:
        mid = (left + right) // 2

        inversions += merge_sort_and_count(arr, temp, left, mid)
        inversions += merge_sort_and_count(arr, temp, mid + 1, right)
        inversions += merge_and_count(arr, temp, left, mid, right)

    return inversions

# Function to count inversions in the array
def count_inversions(arr):
    temp = [0] * len(arr)
    return merge_sort_and_count(arr, temp, 0, len(arr) - 1)

# Example usage
if __name__ == "__main__":
    arr = [8, 4, 2, 1]
    print("Number of inversions:", count_inversions(arr))