Вам дана перестановка длины \(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]\) можно получить при помощи третьей операции (поменять местами третий и четвертый элементы).
Примечание
Напомним, что перестановка \(p\) длины \(n\) лексикографически меньше, чем перестановка \(q\) длины \(n\), если существует такой индекс \(i \le n\), что для всех \(j\) от \(1\) до \(i - 1\) выполняется условие \(p_j = q_j\), а также \(p_i < q_i\). Например:
- \(p = [1, 3, 5, 2, 4]\) меньше, чем \(q = [1, 3, 5, 4, 2]\) (существует такой индекс \(i=4\), что \(p_i < q_i\), а для всех \(j < i\) выполняется \(p_j = q_j\)),
- \(p = [1, 2]\) меньше, чем \(q = [2, 1]\) (существует такой индекс \(i=1\), что \(p_i < q_i\), а для всех \(j < i\) выполняется \(p_j = q_j\)).