Изменения

Возьмем и отсортируем группы по первому элементу(в случае равенства по последнему). Это можно сделать любой квадратичной или более быстрой сортировкой которая требует дополнительной памяти не больше чем <tex> О(1) </tex>, например сортировка выбором. Следует заметить что после сортировки этих групп элементы которые стоять левее заданного и больше его с противоположного куска отсортированного массива, также они находятся в пределах одной группы, поэтому количество инверсий для каждого элемента не больше <tex> \sqrt{n} </tex>.

Так как кусков <tex> \sqrt{n} </tex> количество операций на этом шаге <tex> O(n) </tex>.