Problem - Count Inversions

Given an array, count the number of inversions: pairs $(i, j)$ where $i < j$ but $a[i] > a[j]$. Example: $[2, 4, 1, 3, 5]$ has 3 inversions: $(2,1), (4,1), (4,3)$.

Naive approach: check all pairs in $O(n^2)$. BIT approach: process right to left. For each element, query how many smaller elements you've seen so far (to the right).

This counts inversions. Constraints: up to $10^5$ elements.