Задача . D. Перевертыш

Вам дана перестановка \(p\) длины \(n\).

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

К перестановке \(p\) нужно ровно один раз применить следующую операцию:

• Сначала вы выбираете отрезок \([l, r]\) (\(1 \le l \le r \le n\), отрезок —непрерывная последовательность чисел \(\{p_l, p_{l+1}, \ldots, p_{r-1}, p_r\}\)) и переворачиваете его. Переворот отрезка означает, что меняются местами пары чисел \((p_l, p_r)\), \((p_{l+1}, p_{r-1})\), ..., \((p_{l + i}, p_{r - i})\) (где \(l + i \le r - i\)).
• Затем вы меняете местами префикс и суффикс: \([r+1, n]\) и \([1, l - 1]\) (обратите внимание, что эти отрезки могут быть пустыми).

Например, \(n = 5, p = \{2, \color{blue}{3}, \color{blue}{1}, 5, 4\}\) и был выбран отрезок \([l = 2, r = 3]\), тогда после переворота отрезка \(p = \{\color{green}{2}, \color{blue}{1}, \color{blue}{3}, \color{green}{5}, \color{green}{4}\}\), затем поменяются местами отрезки \([4, 5]\) и \([1, 1]\). Тогда \(p = \{\color{green}{5}, \color{green}{4}, 1, 3, \color{green}{2}\}\). Можно показать, что это максимальный возможный ответ для данной перестановки.

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

Перестановка \(a\) лексикографически больше перестановки \(b\), если существует \(i\) (\(1 \le i \le n\)) такое, что \(a_j = b_j\) для \(1 \le j < i\) и \(a_i > b_i\).