Вам дана перестановка \(p_1, p_2, \ldots, p_n\) длины \(n\). Вам нужно выбрать два целых числа \(l,r\) (\(1 \le l \le r \le n\)) и развернуть подотрезок \([l,r]\) перестановки. Перестановка станет равной \(p_1,p_2, \dots, p_{l-1},p_r,p_{r-1}, \dots, p_l,p_{r+1},p_{r+2}, \dots ,p_n\).
Найдите лексикографически минимальную перестановку, которая может быть получена в результате применения ровно одной операции разворота для начальной перестановки.
Заметьте, что для двух различных перестановок равной длины \(a\) и \(b\), \(a\) лексикографически меньше \(b\), если в первой позиции, где они отличаются, в \(a\) стоит меньший элемент.
Перестановкой называется массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) является перестановкой, но \([1,2,2]\) не является перестановкой (\(2\) встречается дважды в массиве) и \([1,3,4]\) тоже не является перестановкой (\(n=3\), но \(4\) присутствует в массиве).
Примечание
В первом наборе входных данных длина перестановки равна \(1\), поэтому единственный возможный отрезок \([1,1]\). Итоговая перестановка равна \([1]\).
Во втором наборе входных данных мы можем получить тождественную перестановку с помощью разворота отрезка \([1,2]\). Итоговая перестановка равна \([1,2,3]\).
В третьем наборе входных данных наилучшим возможным отрезком является \([2,3]\). Итоговая перестановка равна \([1,2,4,3]\).
В четвёртом наборе входных данных не существует меньшей перестановки, поэтому мы можем оставить её, выбрав отрезок \([1,1]\). Итоговая перестановка равна \([1,2,3,4,5]\).