Число инверсий

Дан массив из $n$ целых чисел. Его нужно отсортировать по возрастанию, меняя местами только соседние элементы. Какое наименьшее число обменов потребуется?

В первой строке $n$ ($1 \le n \le 2 \cdot 10^5$). Во второй — $n$ целых чисел ($|a_i| \le 10^9$).

Одно число — наименьшее количество обменов.

Каждый обмен соседей устраняет ровно одну инверсию — пару $i < j$ с $a_i > a_j$, поэтому ответ равен числу инверсий. Считайте их внутри сортировки слиянием: когда при слиянии двух отсортированных половин берётся элемент из правой половины, все оставшиеся элементы левой больше него — добавляем столько инверсий. Это $O(n \log n)$; симуляция пузырька — $O(n^2)$.

Равные элементы инверсий не образуют: при равенстве берите из левой половины. Ответ достигает $2 \cdot 10^{10}$ — нужен 64-битный тип. Во втором примере ответ $6$.

Источник: UVa 10810.