Number of inversions

You are given an array of $n$ integers. It must be sorted in increasing order by swapping only adjacent elements. What is the minimum number of swaps?

The first line contains $n$ ($1 \le n \le 2 \cdot 10^5$). The second line contains $n$ integers ($|a_i| \le 10^9$).

A single number — the minimum number of swaps.

Every adjacent swap removes exactly one inversion — a pair $i < j$ with $a_i > a_j$, so the answer is the number of inversions. Count them inside merge sort: when merging two sorted halves takes an element from the right half, all remaining elements of the left half are greater — add that many inversions. This is $O(n \log n)$; simulating bubble sort is $O(n^2)$.

Equal elements form no inversion: on a tie take from the left half. The answer reaches $2 \cdot 10^{10}$ — a 64-bit type is needed. In the second example the answer is $6$.

Source: UVa 10810.