Решение задачи Минимизация перестановки с Codeforces

Вам дана перестановка длины n. Напомним, что перестановкой является массив, состоящий из n различных целых чисел от 1 до n в произвольном порядке. Например, [2,3,1,5,4] — перестановка, но [1,2,2] не перестановка (2 встречается в массиве дважды) и [1,3,4] тоже не перестановка (n=3 но в массиве встречается 4).

Вы можете применить максимум n−1 операцию к заданной перестановке (возможно, что вы не будете совершать никаких операций). i-я операция позволяет вам поменять местами элементы заданной перестановки на позициях i и i+1. Каждая операция может быть применена не больше одного раза. Операции могут быть применены в произвольном порядке.

Вы можете увидеть определение лексикографического сравнения в секции примечаний.

Ваша задача — найти лексикографически минимальную перестановку, которая может быть получена с помощью применения каких-либо из данных операций в каком-либо порядке.

Вам необходимо ответить на q независимых наборов входных данных.

Например, рассмотрим перестановку [5,4,1,3,2]. Минимальная возможная перестановка, которую мы можем получить — [1,5,2,4,3], и мы можем сделать это следующим образом:

выполним вторую операцию (поменяем местами второй и третий элементы) и получим перестановку [5,1,4,3,2];
выполним четвертую операцию (поменяем местами четвертый и пятый элементы) и получим перестановку [5,1,4,2,3];
выполним третью операцию (поменяем местами третий и четвертый элементы) и получим перестановку [5,1,2,4,3].
выполним первую операцию (поменяем местами первый и второй элементы) и получим перестановку [1,5,2,4,3];
Другой пример — [1,2,4,3]. Минимальную возможную перестановку [1,2,3,4] можно получить при помощи третьей операции (поменять местами третий и четвертый элементы).