Count Inversions Solution

Implement inversion counting with BIT. Core idea: an inversion $(i, j)$ with $i < j$ and $a[i] > a[j]$ means $a[i]$ is "out of order" relative to $a[j]$.

Processing right to left: when you see $a[i]$, all elements you've added to the BIT are to the right of position $i$.

Querying for elements smaller than $a[i]$ counts exactly those forming inversions with $a[i]$. Alternative: use merge sort to count inversions. Both approaches are $O(n \log n)$.

BIT is often simpler for competitive programming. Time: $O(n \log n)$. Space: $O(n)$.