Инверсиялар сони

$n$ та бутун сондан иборат массив берилган. Уни фақат қўшни элементларнинг ўрнини алмаштириш орқали ўсиш тартибида саралаш керак. Энг камида нечта алмаштириш керак?

Биринчи қаторда $n$ ($1 \le n \le 2 \cdot 10^5$). Иккинчи қаторда $n$ та бутун сон ($|a_i| \le 10^9$).

Битта сон — алмаштиришларнинг энг кам сони.

Ҳар бир қўшни алмаштириш айнан битта инверсияни — $i < j$ ва $a_i > a_j$ бўлган жуфтликни — йўқ қилади, шунинг учун жавоб инверсиялар сонига тенг. Уларни (бирлаштириб саралаш) ичида сананг: икки сараланган ярмини бирлаштиришда ўнг ярмдан элемент олинса, чап ярмда қолган барча элементлар ундан катта — шунча инверсия қўшилади. Бу ; пуфакча саралашни симуляция қилиш .