Изменения

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