Count inversions in a permutation

Problem

Given an array a of length n that is a permutation of distinct integers (e.g., 1..n), define an inversion as a pair of indices (i, j) such that:

• 0 ≤ i < j < n, and
• a[i] > a[j].

Task

Write a function that returns the number of inversions in the array.

Input/Output

• Input: an integer array a with all distinct values
• Output: a single integer = the number of inversions

Notes

• Any time complexity is acceptable (e.g., an O(n^2) approach is fine), but you may also discuss faster approaches if you know them.