Count Smaller: Multiple Approaches

Approach 1: Process right to left with BIT Process from right.

For each element, query count of smaller in BIT, then add current element. Approach 2: Merge sort During merge sort, count inversions as elements cross from right to left subarray. Approach 3: Wavelet tree Build wavelet tree on $A$.

For each $i$, query countLess in range $[i+1, n-1]$. All approaches give $O(n \log n)$. The BIT approach is simplest for this specific problem. Wavelet tree is overkill here but demonstrates the capability.