Риканутая перестановка

Автор задачи: Полина Шайдурова, разработчики: Полина Шайдурова и Даниил Орешников

Давайте заметим, что при циклическом сдвиге на $$$1$$$ количество инверсий в перестановке меняется достаточно понятным образом. Пусть первым стоял элемент $$$x$$$. Тогда:

Таким образом, при перемещении элемента $$$x$$$ из начала перестановки в конец число инверсий изменяется на $$$n - 2x + 1$$$. Заметим, что, пройдя так целый круг, число инверсий вернется к исходному значению. А значит, чтобы найти минимальное возможное число инверсий, надо найти, на сколько максимум оно может уменьшиться за первые $$$n$$$ циклических сдвигов.

Для этого просто выпишем новый массив $$$b$$$, в котором $$$b_i = n - 2 a_i + 1$$$, посчитаем на нем префиксные суммы (суммарное изменение числа инверсий за первые сколько-то сдвигов) и найдем среди них минимальную. Позиция, на которой префиксные суммы достигают минимума, и будет ответом на задачу. Время работы решения — $$$\mathcal{O}(n)$$$.