Найдите предыдущую в лексикографическом порядке перестановку. Перестановка вида \textbf{N}, \textbf{N-1}, ..., \textbf{3}, \textbf{2}, \textbf{1} является предыдущей для \textbf{1}, \textbf{2}, \textbf{3}, ..., \textbf{N-1}, \textbf{N}. \InputFile В первой строке входного файла записано число \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{10^5}) - количество элементов в перестановке. Во второй строке записана перестановка. \OutputFile В выходной файл вывести \textbf{N} чисел - искомую перестановку.