Если вам разрешено перемещать только первый элемент массива, сколько вставок потребуется для полной сортировки массива?
В выходных данных укажите количество необходимых вставок, а также количество позиций, на которые каждый элемент перемещается назад.
Например:
Ввод:
6
1 4 2 5 3 6
Вывод:
4
3 4 2 4
Объяснение:
Это порядок вставок:
4 2 5 1 3 6
2 5 1 3 4 6
5 1 2 3 4 6
1 2 3 4 5 6
Я могу сделать это в O (n 2 ), поскольку проблема упрощает поиск позиции, в которой первый элемент находится в возрастающем суффиксе массива.
Как решить эту проблему в O (nlogn)?